Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Vehicle routing problems with multiple trips

  • Invited Survey
  • Published:
4OR Aims and scope Submit manuscript

Abstract

This paper presents a survey on the multi-trip vehicle routing problem (MTVRP) and on related routing problems where vehicles are allowed to perform multiple trips. The first part of the paper focuses on the MTVRP. It gives an unified view on mathematical formulations and surveys exact and heuristic approaches. The paper continues with variants of the MTVRP and other families of routing problems where multiple trips are sometimes allowed. For the latter, it specially insists on the motivations for having multiple trips and the algorithmic consequences. The expected contribution of the survey is to give a comprehensive overview on a structural property of routing problems that has seen a strongly growing interest in the last few years and that has been investigated in very different areas of the routing literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Adulyasak Y, Cordeau J-F, Jans R (2014) The production routing problem: a review of formulations and solution algorithms. Comput Oper Res 155:141–152

    Google Scholar 

  • Aghezzaf E-H, Raa B, Van Landeghem H (2006) Modeling inventory routing problems in supply chains of high consumption products. Eur J Oper Res 169(3):1048–1063

    Article  Google Scholar 

  • Alonso F, Alvarez MJ, Beasley JE (2008) A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions. J Oper Res Soc 59(7):963–976

    Article  Google Scholar 

  • Anaya-Arenas AM, Chabot T, Renaud J, Ruiz A (2014) Biomedical sample transportation: a case study based on Quebec’s healthcare supply chain. Technical report, Faculté des sciences de l’administration, Universit Laval Québec (Québec) Canada

  • Avella P, Boccia M, Sforza A (2004) Solving a fuel delivery problem by heuristic and exact approaches. Eur J Oper Res 152(1):170–179

    Article  Google Scholar 

  • Ayadi R, Elldrissi AE, Benadada Y, El Hilali Alaoui A (2014) Evolutionary algorithm for a green vehicle routing problem with multiple trips. In: International conference on logistics and operations management, pp 148–154

  • Azi N (2010) Méthodes Exactes et Heuristiques pour le Problème de Tournées avec Fenêtres de Temps et Réutilisation de Véhicules. PhD thesis, Université de Montréal

  • Azi N, Gendreau M, Potvin J-Y (2007) An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. Eur J Oper Res 178(3):755–766

    Article  Google Scholar 

  • Azi N, Gendreau M, Potvin J-Y (2010) An exact algorithm for a vehicle routing problem with time windows and multiple routes. Eur J Oper Res 202(3):756–763

    Article  Google Scholar 

  • Azi N, Gendreau M, Potvin J-Y (2012) A dynamic vehicle routing problem with multiple delivery routes. Ann Oper Res 199(1):103–112

    Article  Google Scholar 

  • Azi N, Gendreau M, Potvin J-Y (2014) An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Comput Oper Res 41:167–173

    Article  Google Scholar 

  • Battarra M, Monaci M, Vigo D (2009) An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. Comput Oper Res 36(11):3041–3050

    Article  Google Scholar 

  • Bendall HB, Stent AF (2001) A scheduling model for a high speed containership service: a hub and spoke short-sea application. Int J Marit Econ 3:262–277

    Article  Google Scholar 

  • Bertazzi L, Savelsbergh M, Speranza MG (2008) The vehicle routing problem—last advances and new challenges. In: Operations research computer science interfaces, chapter Inventory routing. Springer, pp 49–72

  • Boschetti M, Maniezzo V (2015) A set covering based matheuristic for a real-world city logistics problem. Int Trans Oper Res 22:169–195

    Article  Google Scholar 

  • Brandão J, Mercer A (1997) A tabu search algorithm for the multi-trip vehicle routing problem. Eur J Oper Res 100(1):180–191

    Article  Google Scholar 

  • Brandão J, Mercer A (1998) The multi-trip vehicle routing problem. J Oper Res Soc 49:799–805

    Article  Google Scholar 

  • Buhrkal K, Larsen A, Ropke S (2012) The waste collection vehicle routing problem with time windows in a city logistics context. Procedia Soc Behav Sci 39:241–254

    Article  Google Scholar 

  • Caceres-Cruz J, Grasas A, Ramalhinho H, Juan AA (2014) A savings-based randomized heuristic for the heterogeneous fixed fleet vehicle routing problem with multi-trips. J Appl Oper Res 6(2):69–81

    Google Scholar 

  • Cattaruzza D, Absi N, Feillet D (2016) The multi-trip vehicle routing problem with time windows and release dates. Transp Sci (to appear)

  • Cattaruzza D, Absi N, Feillet D, Vidal T (2014) A memetic algorithm for the multi trip vehicle routing problem. Eur J Oper Res 236(6):833–848

    Article  Google Scholar 

  • Cattaruzza D, Absi N, Feillet D, Vigo D (2014) An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows. Comput Oper Res 51:257–267

    Article  Google Scholar 

  • Ceselli A, Righini G, Salani M (2009) A column generation algorithm for a rich vehicle-routing problem. Transp Sci 43(1):56–69

    Article  Google Scholar 

  • Chang T-C, Lee C-Y (2004) Machine scheduling with job delivery coordination. Eur J Oper Res 158(2):470–487

    Article  Google Scholar 

  • Chbichib A, Mellouli R, Chabchoub H (2012) Profitable vehicle routing problem with multiple trips: modeling and variable neighborhood descent algorithm. Am J Oper Res 2(6):104–119

    Google Scholar 

  • Chen Z-L (2010) Integrated production and outbound distribution scheduling: review and extensions. Oper Res 58(1):130–148

    Article  Google Scholar 

  • Christiansen M, Fagerholt K, Nygreen B, Ronen D (2007) Maritime transportation. In: Handbooks in operations research & management science: transportation, vol 14. Elsevier, North Holland, pp 189–284

  • Christiansen M, Fagerholt K, Ronen D (2004) Ship routing and scheduling: status and perspectives. Transp Sci 38(1):1–18

    Article  Google Scholar 

  • Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. Wiley, Chichester, pp 315–338

    Google Scholar 

  • Cinar D, Gakis K, Pardalos PM (2014) Reduction of CO\(_2\) emissions in cumulative multi-trip vehicle routing problems with limited duration. Environ Model Assess. doi:10.1007/s10666-014-9434-2

  • Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12(4):568–581

    Article  Google Scholar 

  • Coelho LC, Cordeau J-F, Laporte G (2014) Thirty years of inventory routing. Transp Sci 48(1):1–19

    Article  Google Scholar 

  • Cornillier F, Boctor FF, Laporte G, Renaud J (2008) A heuristic for the multi-period petrol station replenishment problem. Eur J Oper Res 191:295–305

    Article  Google Scholar 

  • Cornillier F, Boctor FF, Laporte G, Renaud J (2009) An exact algorithm for the petrol station replenishment problem. J Oper Res Soc 59:607–615

    Article  Google Scholar 

  • Cornillier F, Laporte G, Boctor FF, Renaud J (2009) The petrol station replenishment problem with time windows. Comput Oper Res 36(3):919–935

    Article  Google Scholar 

  • Cornillier G, Boctor FF, Renaud J (2012) Heuristic for the multi-depot petrol station replenishment problem with time windows. Eur J Oper Res 220(2):361–369

    Article  Google Scholar 

  • Crainic TG, Gajapl Y, Gendreau M (2012) Multi-zone multi-trip vehicle routing problem with time windows. Technical Report 2012–36, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada

  • Crevier B, Cordeau J-F, Laporte G (2007) The multi-depot vehicle routing problem with inter-depot routes. Eur J Oper Res 176(2):756–773

    Article  Google Scholar 

  • Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manag Sci 6:80–91

    Article  Google Scholar 

  • Fagerholt K (1999) Optimal fleet design in a ship routing problem. Int Trans Oper Res 9(5):453–464

    Article  Google Scholar 

  • Fagerholt K, Lindstad H (2000) Optimal policies for maintaining a supply service in the norwegian sea. Omega 28(3):269–275

    Article  Google Scholar 

  • Fisher ML (1994) Optimal solution for vehicle routing problem using minimum \(k\)-trees. Oper Res 42(4):626–642

    Article  Google Scholar 

  • Fleischmann B (1990) The vehicle routing problem with multiple use of vehicles. Technical report, Fachbereich Wirtschaftswissenschaften, Universität Hamburg

  • Gehring H, Homberger J (1999) A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: EUROGEN99

  • Geismar HN, Laporte G, Lei L, Sriskandarajah C (2008) The integrated production and transportation scheduling problem for a product with a short lifespan. INFORMS J Comput 20(1):21–33

    Article  Google Scholar 

  • Gianessi P (2014) Solving strategic and tactical optimization problems in city logistics. PhD thesis, Université Paris 13

  • Grangier P, Gendreau M, Lehuédé F, Rousseau L-M (2014) An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. Technical Report 2014–33, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada

  • Gribkovskaia I, Gullberg BO, Hovden KJ, Wallace SW (2006) Optimization model for a livestock collection problem. Int J Phys Distrib Logist Manag 36(2):136–152

    Article  Google Scholar 

  • Gutin G, Punnen AP (2007) The traveling salesman problem and its variations. Combinatorial optimization, vol 12. Springer, Dordrecht. doi:10.1007/b101971

  • Hajri-Gabouj S, Darmoul S (2003) A hybrid evolutionary approach for a vehicle routing problem with double time windows for the depot and multiple use of vehicles. Stud Inform Control 12(4):253–268

    Google Scholar 

  • Halvorsen-Weare EE, Fagerholt K, Nonås LM, Asbjørnslett BE (2012) Optimal fleet composition and periodic routing of offshore supply vessels. Eur J Oper Res 223(2):508–517

    Article  Google Scholar 

  • Hernandez F, Feillet D, Giroudeau R, Naud O (2013) An exact algorithm to solve the multi-trip vehicle routing problem with time windows. Technical report

  • Hernandez F, Feillet D, Giroudeau R, Naud O (2014) A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration. 4OR 12:235–259

    Article  Google Scholar 

  • Koc C, Karaoglan I (2011) A branch and cut algorithm for the vehicle routing problem with multiple use of vehicles. In: Proceedings of the 41st international conference on computers & industrial engineering, Los Angeles, USA, pp 554–559

  • Lee J, Kim B-I, Johnson AL, Lee K (2014) The nuclear medicine production and delivery problem. Eur J Oper Res 236(2):461–472

    Article  Google Scholar 

  • Lei L, Liu S, Ruszczynski A, Park S (2006) On the integrated production, inventory, and distribution routing problem. IIIE Trans 38(11):955–970

    Article  Google Scholar 

  • Lenstra JK, Rinnooy Kan HG (1981) Complexity of vehicle routing and scheduling problems. Networks 11(2):221–227

    Article  Google Scholar 

  • Lin CKY, Kwok RCW (2006) Multi-objective metaheuristic for a location routing problem with multiple use of vehicles on real data and simulated data. Eur J Oper Res 175(3):1833–1849

    Article  Google Scholar 

  • Macedo R, Alves C, Valério de Carvalho JM, Clautiaux F, Hanafi S (2011) Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model. Eur J Oper Res 214(3):536–545

    Article  Google Scholar 

  • Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J ACM 7(4):326–329

    Article  Google Scholar 

  • Mingozzi A, Roberti R, Toth P (2013) An exact algorithm for the multi-trip vehicle routing problem. INFORMS J Comput 25(2):193–207

    Article  Google Scholar 

  • Mu Q, Eglese RW (2013) Disrupted capacitated vehicle routing problem with order release delay. Ann Oper Res 207(1):201–216

    Article  Google Scholar 

  • Nguyen PK, Crainic TG, Toulouse M (2013) A tabu search for time-dependent multi-zone multi-trip vehicle routing problem with time windows. Eur J Oper Res 231(1):43–56

    Article  Google Scholar 

  • Nguyen PK, Crainic TG, Toulouse M (2014) Multi-zone multi-trip pickup and delivery problem with time windows and synchronization. Technical Report 2014–18, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport, Université de Montréal, Montréal, QC, Canada

  • Olivera A, Viera O (2007) Adaptive memory programming for the vehicle routing problem with multiple trips. Comput Oper Res 34(1):28–47

    Article  Google Scholar 

  • Ong JO, Suprayogi (2011) Vehicle routing problem with backhaul, multiple trips and time windows. J Tek Ind 13(1):1–10

    Google Scholar 

  • Oppen J, Løkketangen A (2008) A tabu search approach for the livestock collection problem. Comput Oper Res 35(10):3213–3229

    Article  Google Scholar 

  • Oppen J, Løkketangen A, Desrosiers J (2010) Solving a rich vehicle routing and inventory problem using column generation. Comput Oper Res 37(7):1308–1317

    Article  Google Scholar 

  • Petch RJ, Salhi S (2004) A multi-phase constructive heuristic for the vehicle routing problem with multi trips. Discrete Appl Math 133(1–3):69–92

    Google Scholar 

  • Povlovitsch S, Mendes A Bergsten (2013) Column generation for a multitrip vehicle routing problem with time windows, driver work hours, and heterogeneous fleet. Mathematical problems in engineering, Article ID 824961, 13 pp

  • Prins C (2002) Efficient heuristic for the heterogeneous fleet multitrip VRP with application to a large-scale real case. J Math Model Algorithms 1:135–150

    Article  Google Scholar 

  • Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31(12):1985–2002

    Article  Google Scholar 

  • Raa B, Aghezzaf E-H (2008) Designing distribution patterns for long-term inventory routing with constant demand rates. Int J Prod Econ 112(1):255–263

    Article  Google Scholar 

  • Raa B, Aghezzaf E-H (2009) A practical solution approach for the cyclic inventory routing problem. Eur J Oper Res 192(2):429–441

    Article  Google Scholar 

  • Rivera JC, Afsar HM, Prins C (2014) Multistart evolutionary local search for a disaster relief problem. In: Legrand P, Corsini M-M, Hao J-K, Monmarché N, Lutton E, Schoenauer M (eds) Artificial evolution. 11th International Conference, Evolution Artificielle, EA 2013, Bordeaux, France, October 21–23, 2013. Lecture notes in computer science, vol 8752. Springer, pp 129–141.doi:10.1007/978-3-319-11683-9_11

  • Rochat Y, Taillard É (1995) Probabilistic diversification and intensification in local search for vehicle routing. J Heuristics 1(1):147–167

    Article  Google Scholar 

  • Ronen D (1992) Allocation of trips to trucks operating from a single terminal. Comput Oper Res 19(5):445–451

    Article  Google Scholar 

  • Salhi S (1987) The integration of routing into location-allocation and vehicle fleet composition problems. PhD thesis, university of Lancaster

  • Salhi S, Petch RJ (2007) A GA based heuristic for the vehicle routing problem with multiple trips. J Math Model Algorithms 6(4):591–613

    Article  Google Scholar 

  • Şen A, Bülbül K (2008) A survey on multi trip vehicle routing problem. In: VI international logistics & supply chain congress. Instanbul

  • Shyshou A, Fagerholt K, Gribkovskaia I, Laporte G (2012) A large neighbourhood search heuristic for a periodic supply vessel planning problem arising on offshore oil and gas operations. INFOR 50(4):195–204

    Google Scholar 

  • Solomon MM (1987) Algorithms for the vehicle routing and scheduling problem with time windows constraints. Oper Res 35:254–265

    Article  Google Scholar 

  • Suprayogi, Yamato H, Iskendar (2001) Ship routing design for the oily liquid waste collection. J Soc Nav Archit Jpn 190:325–335

    Article  Google Scholar 

  • Taillard ÉD (1993) Parallel iterative search methods for vehicle routing problems. Networks 23(8):661–673

    Article  Google Scholar 

  • Taillard ÉD, Laporte G, Gendreau M (1996) Vehicle routeing with multiple use of vehicles. J Oper Res Soc 47(8):1065–1070

    Article  Google Scholar 

  • Taniguchi E, Shimamoto H (2004) Intelligent transportation sustem based dynamic vehicle routing and scheduling with variable travel times. Transp Res C 12(3–4):235–250

    Article  Google Scholar 

  • Taniguchi E, Van Der Heijden RECM (2000) An evaluation methodology for the city logistics. Transp Rev 20(1):65–90

    Article  Google Scholar 

  • Toth P, Vigo D (eds) (2002) The vehicle routing problem. SIAM Monographs on discrete mathematics and applications. doi:10.1137/1.9780898718515

  • Tsirimpas P, Tatarakis A, Minis I, Kyriakidis EG (2008) Single vehicle routing with a predefined customer sequence and multiple depot returns. Eur J Oper Res 187(2):483–495

    Article  Google Scholar 

  • Tung DV, Pinnoi A (2000) Vehicle routing-scheduling for waste collection in Hanoi. Eur J Oper Res 125(3):449–468

    Article  Google Scholar 

  • Ullrich AC (2013) Integrated machine scheduling and vehicle routing with time windows. Eur J Oper Res 227(1):152–165

    Article  Google Scholar 

  • Van Buer MG, Woodruff DL, Olson RT (1999) Solving the medium newspaper production/distribution problem. Eur J Oper Res 115(2):237–253

    Article  Google Scholar 

  • Wang Z, Liang W, Hu X (2014) A metaheuristic based on a pool of routes for the vehicle routing problem with multiple trips and time windows. J Oper Res Soc 65:37–48

    Article  Google Scholar 

  • Yellow PC (1970) A computational modification to the savings method of vehicle scheduling. Oper Res Q 21(2):281–283

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Diego Cattaruzza.

Appendices

Appendix 1: Benchmark instances for the MTVRP

Table 3 presents the state-of-the-art results on benchmark instances proposed by Taillard et al. (1996) for the MTVRP. The first column indicates the instance name, the number of customers N and the value \(z^*\) that served as a basis for the construction of the instance. Columns \(\left| {\mathcal {V}}\right| \), \(T_H^1\) and \(T_H^2\) give the number of vehicles and the length of the time horizon. Columns Opt report optimal values when available (all obtained by Mingozzi et al. (2013)). Columns Best Known report best known values (all obtained by the heuristic method proposed in Cattaruzza et al. (2014)), when the corresponding optimal values are not known but feasible solutions have been found. Column Best Unfeas reports the value (including penalty) of the best unfeasible solution, when no feasible solutions are known. This column is omitted for instances corresponding to time horizon \(T_H^2\) since a feasible solution has been found for all instances. All these values and more detailed algorithm comparisons can be found in Cattaruzza et al. (2014). State-of-the-art algorithms are Olivera and Viera (2007) and Cattaruzza et al. (2014).

Table 3 Results on MTVRP instances

Appendix 2: Benchmark instances for the MTVRP with time-windows and service-dependent loading times

Table 4 presents the state-of-the-art results on benchmark instances proposed by Hernandez et al. (2013), and adapted from Solomon’s, for the MTVRP with time-windows and service-dependent loading times. In these instances Q is set to 100 and M is set to 2 (instances with 25 customers) or 4 (instances with 50 customers). Other data are kept as in original instances. Distances are Euclidean and truncated to one decimal place. Column Opt reports optimal values when they are known. Column Best Known reports best known solution values for other instances.

Table 4 Results on MTVRP with time-windows and service-dependent loading times instances

Optimal values are obtained by Hernandez et al. (2013). All the best known values are obtained by the heuristic method proposed in Cattaruzza et al. (2016). Two of these best know values are upper bounds determined by Hernandez et al. (2013) (but no optimality certificate is provided).

Appendix 3: Benchmark instances for the MTVRP with time-windows, service-dependent loading times, limited trip duration and profits

Tables 5 and 6 report state-of-the-art results on benchmark instances proposed by Azi (2010), based on Solomon’s, for the MTVRP with time-windows, service-dependent loading times, limited trip duration and profits (MTVRPTW-LDP). Table 5 reports optimal solution values when all customers are visited. Table 6 gives optimal solutions for which some customers are left non-visited. The problem was investigated by Azi et al. (2010), Macedo et al. (2011) and Hernandez et al. (2014), with the exception that the latter does not allow non-visited vertices.

Table 5 Benchmarks for the MTVRPTW-LDP: exact solutions with all customers visited
Table 6 Benchmarks for the MTVRPTW-LDP: exact solutions with non visited customers

Each instance is solved with two values for N, respectively equal to 25 and 40, and two values for \(T_{max}\). For instances of groups RC and R, \(T_{max}\) is either set to 75 (indicated as Short \(T_{max}\) in Table 5) or 100 (Large \(T_{max}\)). For group C it is set to 220 (Short \(T_{max}\)) or 250 (Large \(T_{max}\)). Service times in C2 instances are equal to 90 for each customer, while in the other cases they are equal to 10. The number of vehicles is set to 2. \(\beta \) = 0.2.

Additionally, two different conventions have been adopted for computing the distance matrix. In Azi et al. (2010), instances are used with distances rounded at the second decimal place. Macedo et al. (2011) performed their experiments on the same instances but without truncating distances. Hernandez et al. (2014) evaluate their approach on both types of distances. Columns Opt(T) and Opt(NT) of Table 5 report the optimal value when the distances are truncated (T) or not truncated (NT), respectively. In Table 6 the objective function is hierarchical and the optimal solution is described by the number of non-visited customers (Column Nb) and the traveled distance (column Dist). Whether distances are truncated or not, we follow the literature by reporting travel distances truncated at the second decimal place.

In both tables a “-” indicates that no optimal solution has been found. In Table 5 NoSol is written instead if it is proved that no solution visiting all customers exist. No heuristic algorithms having been applied to these instances, we do not report upper bounds.

Detailed comparisons of the three approaches when all customers are visited can be found in Hernandez et al. (2014). They permit to conclude that Macedo et al. (2011) and Hernandez et al. (2014) obtain comparable results and significantly improve upon Azi et al. (2010), not forgetting that Hernandez et al. (2014) is more specialized (not allowing non-visited vertices).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cattaruzza, D., Absi, N. & Feillet, D. Vehicle routing problems with multiple trips. 4OR-Q J Oper Res 14, 223–259 (2016). https://doi.org/10.1007/s10288-016-0306-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-016-0306-2

Keywords

Mathematics Subject Classification

Navigation