Transportation Science · 2011 · 109 citations · 21 references
Natural SciencesTransportation PlanningOptimizationTransportTransportationCombinatorial OptimizationDiscrete OptimizationInteger ProgrammingMathematical ProgrammingNetwork OptimizationRouting AlgorithmsBranch-and-cutCut AlgorithmsInteger Linear ProgrammingLinear Integer OptimizationMulticommodity FlowRouting ProblemsVehicle RoutingVehicle Routing Problems
The generalized vehicle routing problem (GVRP) consists of finding a set of routes for a number of capacitated vehicles on a graph where the vertices are partitioned into clusters with given demands, such that the total cost of travel is minimized and all demands are met. This paper describes and compares four new integer linear programming formulations for the GVRP, two based on multicommodity flow and the other two based on exponential-size sets of inequalities. Branch-and-cut algorithms are proposed for the latter two. Computational results on a large set of instances are presented.
21
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations