Skip to main content
Top

2021 | OriginalPaper | Chapter

6. Linear Complexity Algorithms for Visually Appealing Routes in the Vehicle Routing Problem

Authors : Philip Kilby, Dan C. Popescu

Published in: Data and Decision Sciences in Action 2

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The vehicle routing problem consists of finding cost-effective routes for fleets of trucks to serve customers. Logistics managers often prefer routes to also be “visually appealing” because of the better flexibility they provide in coping with small alterations, required due to last-minute or unforeseen events. Compactness of the routes is a key desirable feature, and it can be accomplished by minimizing the area enclosed by the routes. A common approach in the literature relies on imposing a penalty on the area of the convex hull. We propose to use new features which are well correlated with the convex hull area but are significantly easier to implement, having O(n) computational complexity instead of \(O(n \hbox {log} n)\). By accepting only a minimal loss of quality with respect to a primary objective function, like the routes’ total length, we show that area-type penalties can be effective in providing good guidance: construction methods which are based on insertion are naturally steered towards routes displaying more attractive shapes. Used in conjunction with an adaptive large neighbourhood search, our new proposed features lead to routes that exhibit similar compactness compared to using a convex hull area penalty. We also achieve good separation between routes.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
We could of course continue this process of angle orientation refinement. However, it turns out that adding one more level of angle subdivision would require considering another four rotations, then another eight rotations for the next level of refinement and so on. We believe any such additional computational effort is not justified for achieving no more than \(8{\%}\) additional accuracy.
 
Literature
1.
go back to reference Golden B, Raghaven S, Wasil E (eds) (2008) The vehicle routing problem: latest advances and challenges. Springer, Berlin Golden B, Raghaven S, Wasil E (eds) (2008) The vehicle routing problem: latest advances and challenges. Springer, Berlin
2.
go back to reference Toth P, Vigo D (eds) (2014) Vehicle routing: problems, methods and applications. MOS-SIAM series on optimzation. SIAM Toth P, Vigo D (eds) (2014) Vehicle routing: problems, methods and applications. MOS-SIAM series on optimzation. SIAM
3.
go back to reference Hollis BL, Green PJ (2012) Real-life vehicle routing with time windows for visual attractiveness and operational robustness. Asia Pac J Oper Res 29(4) Hollis BL, Green PJ (2012) Real-life vehicle routing with time windows for visual attractiveness and operational robustness. Asia Pac J Oper Res 29(4)
4.
go back to reference Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inf Process Lett 1:132–133CrossRef Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inf Process Lett 1:132–133CrossRef
5.
go back to reference Jarvis RA (1973) On the identification of the convex hull of a finite set of points in the plane. Inf Process Lett 2:18–21CrossRef Jarvis RA (1973) On the identification of the convex hull of a finite set of points in the plane. Inf Process Lett 2:18–21CrossRef
6.
go back to reference Preparata FP, Shamos IM (1985) Computational geometry, 2nd edn. Springer, New YorkCrossRef Preparata FP, Shamos IM (1985) Computational geometry, 2nd edn. Springer, New YorkCrossRef
7.
go back to reference Poot A, Kant G, Wagelmans APM (2002) A savings based method for real-life vehicle routing problems. J Oper Res Soc 53(1):57–68CrossRef Poot A, Kant G, Wagelmans APM (2002) A savings based method for real-life vehicle routing problems. J Oper Res Soc 53(1):57–68CrossRef
8.
go back to reference Tang H, Miller-Hooks E (2006) Interactive heuristic for practical vehicle routing problem with solution shape constraints. Transp Res Rec: J Transp Res Board J 1964(1):9–18CrossRef Tang H, Miller-Hooks E (2006) Interactive heuristic for practical vehicle routing problem with solution shape constraints. Transp Res Rec: J Transp Res Board J 1964(1):9–18CrossRef
9.
go back to reference Hollis BL (2010) Vehicle and crew routing and scheduling. PhD Thesis, School of Mathematics and Physics, The University of Queensland Hollis BL (2010) Vehicle and crew routing and scheduling. PhD Thesis, School of Mathematics and Physics, The University of Queensland
10.
go back to reference Kilby P, Prosser P, Shaw P (1999) Guided local search for the vehicle routing problem. In: Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer Academic, pp 473–486 Kilby P, Prosser P, Shaw P (1999) Guided local search for the vehicle routing problem. In: Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer Academic, pp 473–486
11.
go back to reference Dougherty G (2013) Pattern recognition and classification. Springer, New YorkCrossRef Dougherty G (2013) Pattern recognition and classification. Springer, New YorkCrossRef
12.
go back to reference Kilby P, Verden A (2011) Flexible routing combing constraint programming, large neighbourhood search, and feature-based insertion. In: Proceedings 2nd workshop on artificial intelligence and logistics, (AILOG-2011), pp 43–48 Kilby P, Verden A (2011) Flexible routing combing constraint programming, large neighbourhood search, and feature-based insertion. In: Proceedings 2nd workshop on artificial intelligence and logistics, (AILOG-2011), pp 43–48
13.
go back to reference Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40(4):455–472CrossRef Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40(4):455–472CrossRef
14.
go back to reference Azi N, Gendreau M, Potvin JY (2006) An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Comput Oper Res 41:167–173 Azi N, Gendreau M, Potvin JY (2006) An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Comput Oper Res 41:167–173
15.
go back to reference Bent R, Van HP (2006) A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Comput Oper Res 33(4):875–893CrossRef Bent R, Van HP (2006) A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Comput Oper Res 33(4):875–893CrossRef
16.
go back to reference Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An adaptive large neighborhood search heuristic for two-Echelon vehicle routing problems arising in city logistics. Comput Oper Res 39(12):3215–3228MathSciNetCrossRef Hemmelmayr VC, Cordeau JF, Crainic TG (2012) An adaptive large neighborhood search heuristic for two-Echelon vehicle routing problems arising in city logistics. Comput Oper Res 39(12):3215–3228MathSciNetCrossRef
17.
go back to reference Koç Ç, Bektaş T, Jabali O, Laporte G (2016) The impact of depot location, fleet composition and routing on emissions in city logistics. Transp Res Part B: Methodol 84:81–102CrossRef Koç Ç, Bektaş T, Jabali O, Laporte G (2016) The impact of depot location, fleet composition and routing on emissions in city logistics. Transp Res Part B: Methodol 84:81–102CrossRef
18.
go back to reference Mancini S (2016) A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: formulation and adaptive large neighborhood search based matheuristic. Transp Res Part C: Emerg Technol 70(7):100–112CrossRef Mancini S (2016) A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: formulation and adaptive large neighborhood search based matheuristic. Transp Res Part C: Emerg Technol 70(7):100–112CrossRef
19.
go back to reference Pillac V, Guéret C, Medaglia AL (2013) A parallel matheuristic for the technician routing and scheduling problem. Optim Lett 7(7) Pillac V, Guéret C, Medaglia AL (2013) A parallel matheuristic for the technician routing and scheduling problem. Optim Lett 7(7)
21.
go back to reference Dayarian I, Crainic TG, Gendreau M, Rei W (2016) An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem. Transp Res Part E: Logist Transp Rev 95:95–123CrossRef Dayarian I, Crainic TG, Gendreau M, Rei W (2016) An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem. Transp Res Part E: Logist Transp Rev 95:95–123CrossRef
22.
23.
go back to reference Taillard ED, Gambardella LM, Gendreau M, Potvin J-Y (2001) Adaptive memory programming: a unified view of metaheuristics. Eur J Oper Res 135(1):1–16MathSciNetCrossRef Taillard ED, Gambardella LM, Gendreau M, Potvin J-Y (2001) Adaptive memory programming: a unified view of metaheuristics. Eur J Oper Res 135(1):1–16MathSciNetCrossRef
24.
Metadata
Title
Linear Complexity Algorithms for Visually Appealing Routes in the Vehicle Routing Problem
Authors
Philip Kilby
Dan C. Popescu
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-60135-5_6