A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. (English) Zbl 1205.90081
Summary: This article presents a robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem (HFVRP), in which vehicles may have distinct capacities and costs. The columns in the formulation are associated to q-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudopolynomial time. Powerful new families of cuts are also proposed, which are expressed over a very large set of variables. Those cuts do not increase the complexity of the pricing subproblem. Experiments are reported where instances with up to 75 vertices are solved to optimality, a major improvement with respect to previous algorithms.
MSC:
| 90B20 | Traffic problems in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Software:
CVRPSPReferences:
| [1] | Baldacci, The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem, Comput Oper Res 33 pp 2667– (2006) · Zbl 1086.90002 |
| [2] | Choi, A column generation approach to the heterogeneous fleet vehicle routing problem, Comput Oper Res 34 pp 2080– (2007) · Zbl 1187.90094 |
| [3] | Christofides, Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Math Program 20 pp 255– (1981) · Zbl 0461.90067 |
| [4] | Fukasawa, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math Program 106 pp 491– (2006) · Zbl 1094.90050 |
| [5] | Gendreau, A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Comput Oper Res 26 pp 1153– (1999) · Zbl 0967.90019 |
| [6] | Golden, The fleet size and mix vehicle routing problem, Comput Oper Res 11 pp 49– (1984) · Zbl 0607.90043 |
| [7] | Houck, The travelling salesman problem as a constrained shortest path problem, Opsearch 17 pp 93– (1980) · Zbl 0446.90084 |
| [8] | Irnich, The shortest path problem with resource constraints and k-cycle elimination for kâ{\yen} 3, INFORMS J Comput 18 pp 391– (2006) · Zbl 1241.90161 |
| [9] | Lysgaard, A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math Program 100 pp 423– (2004) · Zbl 1073.90068 |
| [10] | Ochi, A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet, Future Gen Comput Syst 14 pp 285– (1998) |
| [11] | Pessoa 4525 pp 150– (2007) |
| [12] | Picard, The time-dependant traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Oper Res 26 pp 86– (1978) · Zbl 0371.90066 |
| [13] | Poggi de Aragão, âInteger program reformulation for robust branch-and-cut-and-price,â Annals of mathematical programming in Rio pp 56– (2003) |
| [14] | Renaud, A sweep-based algorithm for the fleet size and mix vehicle routing problem, Eur J Oper Res 140 pp 618– (2002) · Zbl 0998.90016 |
| [15] | Taillard, A heuristic column generation method for the heterogeneous fleet VRP, RAIRO 33 pp 1– (1999) · Zbl 0992.90008 |
| [16] | Uchoa, Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, Math Program 112 pp 443– (2008) · Zbl 1146.90059 |
| [17] | Wassan, Tabu search variants for the mix fleet vehicle routing problem, J Oper Res Soc 53 pp 768– (2002) · Zbl 1130.90311 |
| [18] | Westerlund, âMathematical formulations of the heterogeneous fleet vehicle routing problem,â ROUTE 2003, International Workshop on Vehicle Routing pp 1– (2003) |
| [19] | Yaman, Formulations and valid inequalities for the heterogeneous vehicle routing problem, Math Program 106 pp 365– (2006) · Zbl 1134.90527 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
