×

A continuous approximation model for the fleet composition problem on the rectangular grid. (English) Zbl 1371.90026

Summary: A continuous approximation (CA) model is proposed for the fleet composition problem in rectangular grid networks. The model extends O. Jabali et al.’s [“A continuous approximation model for the fleet composition problem”, Transp. Res. Part B 46; No. 10, 1591–1606 (2012)] methodology for radial networks. In the model, delivery points are assumed to be uniformly distributed in a square-shaped service region. The region is partitioned into zones, each zone is allocated to one vehicle, and each vehicle has to visit all the delivery points within its zone. The problem involves finding the optimal fleet of vehicles to minimize the total fleet acquisition costs and travel costs. The CA model is compared to a well-known column generation heuristic. Although the two models have similar results, the CA model is much faster with a computation time of less than 1 s for all experiments. Sensitivity analysis is performed on different parameters. Results show that the largest available vehicle is commonly filled to capacity and is used in the mid-section of the service region. Moreover, increasing the time limit constraint has a step-wise impact on the fleet composition.

MSC:

90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Carlsson JG (2012) Dividing a territory among several vehicles. INFORMS J Comput 24(4):565-577 · Zbl 1460.90028 · doi:10.1287/ijoc.1110.0479
[2] Daganzo CF (1984) The length of tours in zones of different shapes. Transp Res Part B 18(2):135-146 · doi:10.1016/0191-2615(84)90027-4
[3] Francis P, Smilowitz K (2006) Modeling techniques for periodic vehicle routing problems. Transp Res Part B 40(10):872-884 · doi:10.1016/j.trb.2005.12.001
[4] Gendreau M, Laporte G, Musaraganyi C, Taillard ÉD (1999) A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Comput Oper Res 26(12):1153-1173 · Zbl 0967.90019 · doi:10.1016/S0305-0548(98)00100-2
[5] Golden BL, Assad AA, Levy L, Gheysens FG (1984) The fleet size and mix vehicle routing problem. Comput Oper Res 11(1):49-66 · Zbl 0607.90043 · doi:10.1016/0305-0548(84)90007-8
[6] Hoff A, Andersson H, Christiansen M, Hasle G, Løkketangen A (2010) Industrial aspects and literature survey: fleet composition and routing. Comput Oper Res 37(12):2041-2061 · Zbl 1231.90091 · doi:10.1016/j.cor.2010.03.015
[7] Jabali O, Gendreau M, Laporte G (2012) A continuous approximation model for the fleet composition problem. Transp Res Part B 46(10):1591-1606 · Zbl 1431.62251 · doi:10.1016/j.trb.2012.06.004
[8] Langevin A, Mbaraga P, Campbell JF (1996) Continuous approximation models in freight distribution: an overview. Transp Res Part B 30(3):163-188 · doi:10.1016/0191-2615(95)00035-6
[9] Langevin A, Soumis F (1989) Design of multiple-vehicle delivery tours satisfying time constraints. Transp Res Part B 23(2):123-138 · doi:10.1016/0191-2615(89)90036-2
[10] Lee YH, Kim JI, Kang KH, Kim KH (2008) A heuristic for vehicle fleet mix problem using tabu search and set partitioning. J Oper Res Soc 59(6):833-841 · Zbl 1153.90359 · doi:10.1057/palgrave.jors.2602421
[11] Newell GF (1980) Traffic flow on transportation networks. MIT Press, Cambridge
[12] Newell GF, Daganzo CF (1986a) Design of multiple-vehicle delivery tours—I: a ring-radial network. Transp Res Part B 20(5):345-363 · doi:10.1016/0191-2615(86)90008-1
[13] Newell GF, Daganzo CF (1986b) Design of multiple vehicle delivery tours—II other metrics. Transp Res Part B 20(5):365-376 · doi:10.1016/0191-2615(86)90009-3
[14] Pessoa A, Poggi de Aragão M, Uchoa E (2007) A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem, Lecture Notes in Computer Science, vol 4525. Springer, Berlin · Zbl 1203.90136
[15] Renaud J, Boctor FF (2002) A sweep-based algorithm for the fleet size and mix vehicle routing problem. Eur J Oper Res 140(3):618-628 · Zbl 0998.90016 · doi:10.1016/S0377-2217(01)00237-5
[16] Salhi S, Rand GK (1993) Incorporating vehicle routing into the vehicle fleet composition problem. Eur J Oper Res 66(3):313-330 · Zbl 0775.90155 · doi:10.1016/0377-2217(93)90220-H
[17] Taillard ÉD (1999) A heuristic column generation method for the heterogeneous fleet VRP. RAIRO Oper Res 33(01):1-14 · Zbl 0992.90008 · doi:10.1051/ro:1999101
[18] Wassan NA, Osman IH (2002) Tabu search variants for the mix fleet vehicle routing problem. J Oper Res Soc 53:768-782 · Zbl 1130.90311 · doi:10.1057/palgrave.jors.2601344
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.