Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. (English) Zbl 1203.90043
Summary: In the well-known vehicle routing problem (VRP), a set of identical vehicles located at a central depot is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two-commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instances.
MSC:
| 90B20 | Traffic problems in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90B06 | Transportation, logistics and supply chain management |
References:
| [1] | Baldacci, An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation, Oper Res 52 pp 723– (2004) · Zbl 1165.90353 |
| [2] | Baldacci 43 (2008) |
| [3] | BrÃ{\currency}ysy, Technical report (2002) |
| [4] | Choi, A column generation approach to the heterogeneous fleet vehicle routing problem, Comput Oper Res 34 pp 2080– (2007) · Zbl 1187.90094 |
| [5] | Christofides, Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation, Math Program 10 pp 255– (1981) · Zbl 0461.90067 |
| [6] | Cordeau 14 pp 367– (2007) |
| [7] | CPLEX, ILOG CPLEX 10.1 callable library, ILOG, Gentilly Cedex, France, 2007. |
| [8] | Dantzig, The truck dispatching problem, Manag Sci 6 pp 80– (1959) · Zbl 0995.90560 |
| [9] | Dell’Amico, Heuristic approaches for the fleet size and mix vehicle routing problem with time windows, Transport Sci 41 pp 516– (2007) |
| [10] | Desrochers, A new heuristic for the fleet size and mix vehicle-routing problem, Comput Oper Res 18 pp 263– (1991) · Zbl 0723.90018 |
| [11] | J.J. Dongarra, Performance of various computers using standard linear equations software, Technical Report CS-89-85, Electrical Engineering and Computer Science Department, University of Tennessee, 2008. Available at: http://www.netlib.org/benchmark/performance.ps. |
| [12] | Dullaert, New heuristics for the fleet size and mix vehicle routing problem with time windows, J Oper Res Soc 53 pp 1232– (2002) · Zbl 1139.90336 |
| [13] | Fukasawa, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math Program Ser A 106 pp 491– (2006) · Zbl 1094.90050 |
| [14] | Gendreau, A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Comput Oper Res 26 pp 1153– (1999) · Zbl 0967.90019 |
| [15] | Gheysens, A comparison of techniques for solving the fleet size and mix vehicle routing problem, OR Spectrum 6 pp 207– (1984) · Zbl 0549.90068 · doi:10.1007/BF01720070 |
| [16] | Gheysens, A new heuristic for determining fleet size and composition, Math Program Stud 26 pp 233– (1986) · Zbl 0585.90064 · doi:10.1007/BFb0121103 |
| [17] | Golden, The fleet size and mix vehicle routing problem, Comput OR 11 pp 49– (1984) · Zbl 0607.90043 |
| [18] | Letchford, Multistars, partial multistars and the capacitated vehicle routing problem, Math Program 94 pp 21– (2002) · Zbl 1023.90073 |
| [19] | Liu, The fleet size and mix vehicle routing problem with time windows, J Oper Res Soc 50 pp 721– (1999) · Zbl 1054.90522 |
| [20] | J. Lysgaard, CVRPSEP: A package of separation routines for the capacitated vehicle routing problem, Technical report, Dept. of Mgt. Science and Logistics, Aarhus School of Business, Aarhus, Denmark, 2003. |
| [21] | Lysgaard, A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math Program Ser. A 100 pp 423– (2004) · Zbl 1073.90068 |
| [22] | Naddef 9 pp 53– (2002) |
| [23] | Nemhauser, Integer and combinatorial optimization (1999) |
| [24] | Ochi, An evolutionary hybrid metaheuristic for solving the vehicle routing problem with heterogeneous fleet, Lect Notes in Computer Science 1391 pp 187– (1998) |
| [25] | Ochi, A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet, Parallel Distributed Process 1388 pp 216– (1998) · doi:10.1007/3-540-64359-1_691 |
| [26] | Osman, Modern Heuristic Search Methods pp 131– (1996) · doi:10.1007/978-1-4613-1361-8 |
| [27] | Pessoa 4525 pp 150– (2007) |
| [28] | 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 |
| [29] | Salhi, Incorporating vehicle routing into the vehicle fleet composition problem, Eur J Oper Res 66 pp 313– (1993) · Zbl 0775.90155 |
| [30] | Taillard, A heuristic column generation method for the heterogeneous fleet VRP, RAIRO Recherche Opér 33 pp 1– (1999) · Zbl 0992.90008 |
| [31] | P.Toth and D.Vigo (Editors), The vehicle routing problem, Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, PA, 2002. · Zbl 0979.00026 |
| [32] | Wassan, Tabu search variants for the mix fleet vehicle routing problem, J Oper Res Soc 53 pp 768– (2002) · Zbl 1130.90311 |
| [33] | Westerlund, ROUTE 2003 (2003) |
| [34] | Yaman, Formulations and valid inequalities for the heterogeneous vehicle routing problem, Math Program Ser A 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.
