Top

Soft Computing

Published in:

01-09-2015 | Focus

Constrained dynamic vehicle routing problems with time windows

Authors: Jesica de Armas, Belén Melián-Batista

Published in: Soft Computing | Issue 9/2015

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

search-config

AI-assisted search

Off

Abstract

This paper tackles two variants of a Dynamic Vehicle Routing Problem with Time Windows as real-world applications of several companies in the Canary Islands, Spain. In these dynamic vehicle routing problems, customer requests can be either known at the beginning of the planning horizon or dynamically revealed over it. Particularly, the problems corresponding to a delivery company and a vending machines company are taken into consideration. In addition to the dynamism feature of these problems, the companies consider several attributes that consist of a fixed heterogeneous fleet of vehicles, multiple time windows, customers priorities and vehicle–customer constraints. This work proposes a metaheuristic procedure to solve these problems. The computational experiments indicate that the proposed method is feasible to solve these real-world problems.

previous article Texture classification using feature selection and kernel-based techniques

next article A self-organizing map to improve vehicle detection in flow monitoring systems

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!

inform now

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!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

http://web.cba.neu.edu/msolomon/problems.htm.

https://sites.google.com/site/gciports/vrptw/dynamic-vrptw.

Table 2

Dynamic customers

Dyn. request	A. time	Dyn. request	A. time
81	14,105	91	21,811
82	27,790	92	21,064
83	19,617	93	14,527
84	14,111	94	15,419
85	9,494	95	19,106
86	21,474	96	20,479
87	31,747	97	7,725
88	19,119	98	25,892
89	17,287	99	12,850
90	30,821	100	15,807

Table 3

Solution example. Insertion of dynamic requests

	\(R1\)	\(R2\)	\(R3\)	\(R4\)	\(R5\)	\(R6\)	\(R1\)	\(R2\)	\(R3\)	\(R4\)	\(R5\)	\(R6\)
Last visited customer	4	5	4	5	4	3	5	6	5	6	5	3
Accumulated infeasibility	0	0	0	0	0	0	0	0	0	0	0	0
	(\(C97\), \(R5\), \(5\), 0)						(\(C85\), \(R3\), \(8\), \(2{,}060\))
Last visited customer	7	8	6	9	7	3	8	9	7	9	8	3
Accumulated infeasibility	0	0	2,060	0	0	0	0	0	2,060	0	1,751	0
	(\(C99\), \(R5\), \(10\), \(1{,}751\))						(\(C81\), \(R4\), \(16\), 0)
Last visited customer	8	9	7	9	8	3	8	9	7	10	8	3
Accumulated infeasibility	0	0	2,060	0	1,751	0	0	0	2,060	0	1,751	0
	(\(C84\), \(R7\), \(17\), 0)						(\(C93\), \(R4\), \(13\), \(3{,}103\))
Last visited customer	8	9	7	10	8	3	9	9	7	10	8	3
Accumulated infeasibility	0	0	2,060	3,103	1,751	0	1,475	0	2,060	3,103	1,751	0
	(\(C94\), \(R1\), \(11\), \(1{,}475\))						(\(C100\), \(R3\), \(11\), \(5{,}425\))
Last visited customer	10	11	8	11	9	3	11	12	9	12	10	3
Accumulated infeasibility	1,475	0	5,425	3,103	1,751	0	1,475	0	5,425	3,103	1,751	0
	(\(C89\), \(R5\), \(12\), \(1{,}751\))						(\(C95\), \(R2\), \(19\), \(2{,}211\))
Last visited customer	11	12	9	12	10	3	12	13	9	12	10	3
Accumulated infeasibility	1,475	2,211	5,425	3,103	1,751	0	14,75	2,211	5,425	3,103	3,592	0
	(\(C88\), \(R5\), \(13\), \(3{,}592\))						(\(C83\), \(R5\), \(13\), \(1{,}751\))
Last visited customer	13	13	10	12	11	3	14	13	10	13	11	3
Accumulated infeasibility	1,475	2,211	5,425	3,103	1,751	0	1,475	2,211	5,425	3,103	3,153	0
	(\(C96\), \(R5\), \(14\), \(3{,}153\))						(\(C92\), \(R1\), \(20\), \(2{,}945\))
Last visited customer	14	13	11	13	11	3	14	13	11	13	11	3
Accumulated infeasibility	2,945	2,211	5,425	3,103	3,153	0	3,776	2,211	5,425	3,103	3,153	0
	(\(C86\), \(R1\), \(21\), \(3{,}776\))						(\(C91\), \(R3\), \(12\), \(5{,}425\))
Last visited customer	17	16	11	13	14	3	19	17	12	14	14	3
Accumulated infeasibility	3,776	2,211	5,425	3,103	3,153	0	3,776	4,814	5,425	3,103	3,153	0
	(\(C98\), \(R2\), \(20\), \(4{,}814\))						(\(C82\), \(R4\), \(15\), \(8{,}586\))
Last visited customer	21	18	12	15	16	3	22	19	13	15	16	3
Accumulated infeasibility	3,776	4,814	5,425	8,586	3,153	0	3,776	4,814	5,425	8,586	8,332	0
	(\(C90\), \(R5\), \(17\), \(8{,}332\))						(\(C87\), \(R5\), \(17\), \(8{,}612\))

http://www.fernuniversitaet-hagen.de/WINF/inhalte/benchmark_data.htm.

Bräysy O (2003) A reactive variable neighborhood search for the vehicle routing problem with time windows. INFORMS J Comput 15:347–368MathSciNetCrossRef

Cassani L, Righini G (2004) Heuristic algorithms for the tsp with rear-loading. In: 35th Annual Conference of the Italian Operations Research Society (AIRO XXXV), Lecce, Italy

Chen ZL, Xu H (2006) Dynamic column generation for dynamic vehicle routing with time windows. Transp Sci 40(1):74–88CrossRef

Croes GA (1958) A method for solving traveling-salesman problems. Oper Res 6(6):791–812MathSciNetCrossRef

De Armas J, Melián-Batista B, Moreno-Pérez JA, Brito J (2013) GVNS for a real-world rich vehicle routing problem with time windows. University of La Laguna, Technical report

Fleszar K, Osman I, Hindi K (2008) A variable neighbourhood search algorithm for the open vehicle routing problem. Eur J Oper Res 195(3):803–809CrossRef

Gendreau M, Potvin JY (eds) (2004) Focused section on real-time fleet management, vol 38. Transportation Science

Michel Gendreau, Alain Hertz, Gilbert Laporte (1992) New insertion and postoptimization procedures for the traveling salesman problem. Oper Res 40(6):1086–1094MathSciNetCrossRef

Ghiani G, Guerriero F, Laporte G, Musmanno R (2003) Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies. Eur J Oper Res 151:1–11

Goel A, Gruhn V (2008) A general vehicle routing problem. Eur J Oper Res 191(3):650–660MathSciNetCrossRef

Hansen P, Mladenovic N, Moreno-Pérez JA (2010) Variable neighbourhood search: methods and applications. Ann OR 175(1):367–407CrossRef

Hemmelmayr V, Doerner K, Hartl R (2009) A variable neighborhood search heuristic for periodic routing problems. Eur J Oper Res 195(3):791–802CrossRef

Hong L (2012) An improved LNS algorithm for real-time vehicle routing problem with time windows. Comput Oper Res 39(2):151–163CrossRef

Ichoua S, Gendreau M, Potvin J-Y (2007) In: Zeimpekis V, Tarantilis CD, Giaglis GM, Minis I (eds) Planned route optimization for real-time vehicle routing., Dynamic fleet management, volume 38 of operations research/computer science interfaces seriesSpringer, US, pp 1–8

Nicolas J, Frederic S, El-Ghazali T (2008) Multi-objective vehicle routing problems. Eur J Oper Res 189(2):293–309CrossRef

Khouadjia MR, Sarasola B, Alba E, Jourdan L, Talbi EG (2012) A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests. Appl Soft Comput 12(4):1426–1439CrossRef

Kytöjoki J, Nuortio T, Brysy O, Gendreau M (2007) An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Comput Oper Res 34(9):2743–2757CrossRef

Lackner A (2004) Selection meta-heuristics for dynamic vehicle routing problem (Dynamische Tourenplanung mit ausgewählten Metaheuristiken). Number 47. Göttinger Wirtschftinformatik

Larsen A (2001) The dynamic vehicle routing problem. Ph.D. Thesis

Larsen A, Madsen OBG, Solomon MM (2008) In: Golden B, Raghavan S, Wasil E (eds) Recent developments in dynamic vehicle routing systems., The Vehicle Routing Problem: Latest Advances and New Challenges, volume 43 of Operations Research/Computer Science InterfacesSpringer, US, pp 199–218

Lund K, Madsen OBG, Rygaard JM (1996) Vehicle routing problems with varying degrees of dynamism. Technical Report, IMM Institute of Mathematical Modelling

Montemanni R, Gambardella LM, Rizzoli AE, Donati A (2005) Ant colony system for a dynamic vehicle routing problem. J Comb Optim 10(4):327–343MathSciNetCrossRef

Ilhan O (1976) Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Xerox University Microfilms

Pillac V, Gendreau M, Gueret C, Medaglia AL (2013) A review of dynamic vehicle routing problems. Eur J Oper Res 225(1):1–11MathSciNetCrossRef

Polacek M, Hartl K, Doerner K, Reimann M (2004) A variable neighborhood search for the multi depot vehicle routing problem with time windows. J Heuristics 10(6):613–627CrossRef

Psaraftis HN (1980) A Dynamic-programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transp Sci 14(2):130–154CrossRef

Rizzoli AE, Montemanni R, Lucibello E, Gambardella LM (2007) Ant colony optimization for real-world vehicle routing problems. Swarm Intel 1:135–151CrossRef

Solomon MM (1987) Algorithms for the vehicle-routing and scheduling problems with time window constraints. Oper Res 35(2):254–265MathSciNetCrossRef

Taillard E, Badeau P, Gendreau M, Guertin F, Potvin JY (1997) A tabu search heuristic for the vehicle routing problem with soft time windows. Transp Sci 31(2):170–186CrossRef

Title: Constrained dynamic vehicle routing problems with time windows
Authors: Jesica de Armas
Belén Melián-Batista
Publication date: 01-09-2015
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 9/2015
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-014-1574-4

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 9/2015

Border-sensitive learning in generalized learning vector quantization: an alternative to support vector machines

Algebraic study to generalized Bosbach states on residuated lattices

Population statistics for particle swarm optimization: Single-evaluation methods in noisy optimization problems

A Soft-Computing basis for robots’ cognitive autonomous learning

Special issue on advances in computational intelligence and machine learning (IWANN 2013)

Texture classification using feature selection and kernel-based techniques

Premium Partner