Skip to main content
SpringerLink
Log in

A customer-centric routing problem with multiple trips of a single vehicle

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

In this study, we introduce a routing problem with multiple uses of a single vehicle and service time in demand points, minimizing the sum of clients’ waiting time to receive service. This problem is relevant in the distribution of aid in disaster-stricken communities, in the recollection and/or delivery of perishable goods and personnel transportation, among other situations, where reaching clients to perform service, fast and fair, is a priority. We consider vehicle capacity and travel distance constraints, forcing multiple use of the vehicle during the planning horizon. This paper presents two mixed integer formulations for this problem, based on a multi-level network, as well as a metaheuristic algorithm. The proposed models can solve to optimality instances with up to 30 clients. The proposed metaheuristic algorithm obtains high-quality solutions in short computational times.

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

Access this article

Log in via an institution

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.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4

Similar content being viewed by others

References

  • Abeledo H, Fukasawa R, Pessoa AA and Uchoa E (2013). The time dependent traveling salesman problem: Polyhedra and algorithm. Mathematical Programming Computation 5 (1): 27–55.

    Article  Google Scholar 

  • Adenso-Diaz B and Laguna M (2006). Fine-tuning of algorithms using fractional experimental designs and local search. Operations Research 54 (1): 99–114.

    Article  Google Scholar 

  • Alonso F, Alvarez M and Beasley JE (2008). A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions. Journal of the Operational Research Society 59 (7): 963–976.

    Article  Google Scholar 

  • Angel-Bello F, Alvarez A and García I (2013). Two improved formulations for the minimum latency problem. Applied Mathematical Modelling 37 (4): 2257–2266.

    Article  Google Scholar 

  • Avella P, Boccia M and Sforza A (2004). Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research 152 (1): 170–179.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Azi N, Gendreau M and Potvin J-Y (2010). An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. European Journal of Operational Research 202 (3): 756–763.

    Article  Google Scholar 

  • Brandão J and Mercer A (1997). A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal of Operational Research 100 (1): 180–191.

    Article  Google Scholar 

  • Camci F (2013). The travelling maintainer problem: Integration of condition-based maintenance with the travelling salesman problem. Journal of the Operational Research Society 65 (9): 1423–1436.

    Article  Google Scholar 

  • Christofides N, Mingozzi A, Toth P and Sandi C (eds) (1979). The vehicle routing problem. In: Combinatorial Optimization. Wiley: Chichester, pp 315–338.

    Google Scholar 

  • Cordeau J-F, Gendreau M and Laporte G (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30 (2): 105–119.

    Article  Google Scholar 

  • Cornillier F, Laporte G, Boctor FF and Renaud J (2009). The petrol station replenishment problem with time windows. Computers & Operations Research 36 (3): 919–935.

    Article  Google Scholar 

  • Feo TA and Resende MG (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization 6 (2): 109–133.

    Article  Google Scholar 

  • Festa P and Resende M (2011). GRASP: Basic components and enhancements. Telecommunication Systems 46 (3): 253–271.

    Article  Google Scholar 

  • Golden BL, Wasil EA, Kelly JP and Chao IM (1998). Metaheuristics in vehicle routing. In: Crainic TG and Laporte G (eds). Fleet Management and Logistics. Kluwer: Boston, MA, pp 33–56.

    Chapter  Google Scholar 

  • Gouveia L and Voss S (1995). A classification of formulations for the (time-dependent) traveling salesman problem. European Journal of Operational Research 83 (1): 69–82.

    Article  Google Scholar 

  • Ke L and Feng Z (2013). A two-phase metaheuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research 40 (2): 633–638.

    Article  Google Scholar 

  • Koc C and Karaoglan I (2011). A branch and cut algorithm for the vehicle routing problem with multiple use of vehicles. In: 41st International Conference on Computers & Industrial Engineering, pp 554–559.

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

    Article  Google Scholar 

  • Martínez L and Amaya C (2012). A vehicle routing problem with multi-trips and time windows for circular items. Journal of the Operational Research Society 64 (11): 1–14.

    Google Scholar 

  • Mattos Ribeiro G and Laporte G (2012). An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research 39 (3): 728–735.

    Article  Google Scholar 

  • Méndez-Díaz I, Zabala P and Lucena A (2008). A new formulation for the traveling deliveryman problem. Discrete Applied Mathematics 156 (17): 3223–3237.

    Article  Google Scholar 

  • Ngueveu SU, Prins C and Calvo RW (2010). An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Computers & Operations Research 37 (11): 1877–1885.

    Article  Google Scholar 

  • Olivera A and Viera O (2007). Adaptive memory programming for the vehicle routing problem with multiple trips. Computers & Operations Research 34 (1): 28–47.

    Article  Google Scholar 

  • Petch R and Salhi S (2003). A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discrete Applied Mathematics 133 (1–3): 69–92.

    Article  Google Scholar 

  • Picard JC and Queyranne M (1978). The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Operations Research 26 (1): 86–110.

    Article  Google Scholar 

  • Salehipour A, Sörensen K, Goos P and Bräysy O (2008). An efficient GRASP+VND metaheuristic for the traveling repairman problem. Technical report, University of Antwerp, Faculty of Applied Economics.

  • Salehipour A, Sörensen K, Goos P and Bräysy O (2011). Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem. 4OR—A Quarterly Journal of Operations Research 9 (2): 189–209.

    Article  Google Scholar 

  • Şen A and Bülbül K (2008). A survey on multi trip vehicle routing problem. In: VI. International Logistics and Supply Chain Congress, Istanbul, Turkey. İstanbul Bilgi Üniversitesi.

  • Silva MM, Subramanian A, Vidal T and Ochi LS (2012). A simple and effective metaheuristic for the minimum latency problem. European Journal of Operational Research 221 (3): 513–520.

    Article  Google Scholar 

  • Taillard ED, Laporte G and Gendreau M (1995). Vehicle routeing with multiple use of vehicles. Journal of the Operation Research Society 47 (8): 1065–1070.

    Article  Google Scholar 

  • Toth P and Vigo D (eds) (2002). The Vehicle Routing Problem. Society for Industrial and Applied Mathematics: Philadelphia, PA.

    Book  Google Scholar 

  • Vidal T, Crainic T, Gendreau M and Prins C (2013). A unified solution framework for multi-attribute vehicle routing problems. Technical Report 2013-22, CIRRELT.

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

    Article  Google Scholar 

Download references

Acknowledgements

This work is partially supported by the Research Chair in Industrial Engineering of Tecnológico de Monterrey (ITESM Research Fund CAT128) and the Universidad Autónoma de Nuevo León (PAICYT IT764-11). These grants are gratefully acknowledged.

Author information

Authors and Affiliations

  1. Universidad Autónoma de Nuevo León, Nuevo León, México

    Iris Martínez-Salazar & Ada Alvarez

  2. Tecnológico de Monterrey, Nuevo León, México

    Francisco Angel-Bello

Authors
  1. Iris Martínez-Salazar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Francisco Angel-Bello
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ada Alvarez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Iris Martínez-Salazar.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Martínez-Salazar, I., Angel-Bello, F. & Alvarez, A. A customer-centric routing problem with multiple trips of a single vehicle. J Oper Res Soc 66, 1312–1323 (2015). https://doi.org/10.1057/jors.2014.92

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2014.92

Keywords

Search

Navigation