A hybrid genetic/Benders' algorithm with applications to vehicle routing and scheduling problems

This thesis is concerned with heuristic methods for vehicle routing problems (VRPs) utilizing genetic algorithms (GAs). Vehicle routing problems, being in general tightly constrained, have presented difficulties for genetic algorithms, as solutions generated by the crossover and mutation operations of GA must in general be adjusted in order to meet the many restrictions typically encountered, e.g., time windows and route length constraints.; We have included the solution of a real-world multiple-objective vehicle routing problem by a hybrid algorithm which partitions the decisions into that of assigning customers to routes (decisions assigned to a genetic algorithm) and that of sequencing the customers on the routes (decisions assigned to a traveling salesman heuristic algorithm).; Benders' decomposition or partitioning is widely-used technique for partitioning decision variables and assigning the task of selecting these variables to two interacting problems: the master problem which proposes values for the "hard" decisions and the subproblem which makes the "easy" decisions based upon those decisions proposed by the master problem (and in turn provides information in the form of dual variables to guide the master problem to making better decisions).; The classical capacitated plant location (CPL) problem has been used as a simple illustration of the implementation of a hybrid Genetic/Benders' algorithm in which the unconstrained master problem (selecting locations) is solved by a genetic algorithm, while the easier decisions, allocating plant capacity to customers, are made by a subproblem (a classical transportation problem). Solutions generated by this approach are competitive with those obtained by Benders' original algorithm at a tremendous savings in computational effort.; Following the success of the hybrid GA/Benders' algorithm for the CPL problem, this dissertation develops a multi-commodity flow model of the VRP, and uses Benders' decomposition to partition the variables: one set for the routing of vehicles and the other for the routing of commodities. We then assign the difficult vehicle routing decisions to a loosely-constrained master problem which is amenable to a GA, while the more troublesome constraints are imposed on the commodity flows in the more easily-solved network flow subproblem.