Tackling a VRP challenge to redistribute scarce equipment within time windows using metaheuristic algorithms

Ahmed Kheiri, Alina G. Dragomir, David Mueller, Joaquim Gromicho, Caroline Jagtenberg, Jelke J. van Hoorn

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

This paper reports on the results of the VeRoLog Solver Challenge 2016–2017: the third solver challenge facilitated by VeRoLog, the EURO Working Group on Vehicle Routing and Logistics Optimization. The authors are the winners of second and third places, combined with members of the challenge organizing committee. The problem central to the challenge was a rich VRP: expensive and, therefore, scarce equipment was to be redistributed over customer locations within time windows. The difficulty was in creating combinations of pickups and deliveries that reduce the amount of equipment needed to execute the schedule, as well as the lengths of the routes and the number of vehicles used. This paper gives a description of the solution methods of the above-mentioned participants. The second place method involves sequences of 22 low level heuristics: each of these heuristics is associated with a transition probability to move to another low level heuristic. A randomly drawn sequence of these heuristics is applied to an initial solution, after which the probabilities are updated depending on whether or not this sequence improved the objective value, hence increasing the chance of selecting the sequences that generate improved solutions. The third place method decomposes the problem into two independent parts: first, it schedules the delivery days for all requests using a genetic algorithm. Each schedule in the genetic algorithm is evaluated by estimating its cost using a deterministic routing algorithm that constructs feasible routes for each day. After spending 80 percent of time in this phase, the last 20 percent of the computation time is spent on Variable Neighborhood Descent to further improve the routes found by the deterministic routing algorithm. This article finishes with an in-depth comparison of the results of the two approaches.

Original languageEnglish
JournalEURO Journal on Transportation and Logistics
DOIs
Publication statusAccepted/In press - 2019

Fingerprint

Time Windows
Routing algorithms
Metaheuristics
heuristics
Genetic algorithms
Heuristics
Cost estimating
Schedule
Vehicle routing
Pickups
Deterministic Algorithm
Routing Algorithm
Percent
Logistics
Genetic Algorithm
Pickup and Delivery
Vehicle Routing
working group
Descent
Transition Probability

Keywords

  • Evolutionary computations
  • Inventory
  • Metaheuristics
  • Routing

Cite this

@article{ec640d4402d249a882992c2353fac1fc,
title = "Tackling a VRP challenge to redistribute scarce equipment within time windows using metaheuristic algorithms",
abstract = "This paper reports on the results of the VeRoLog Solver Challenge 2016–2017: the third solver challenge facilitated by VeRoLog, the EURO Working Group on Vehicle Routing and Logistics Optimization. The authors are the winners of second and third places, combined with members of the challenge organizing committee. The problem central to the challenge was a rich VRP: expensive and, therefore, scarce equipment was to be redistributed over customer locations within time windows. The difficulty was in creating combinations of pickups and deliveries that reduce the amount of equipment needed to execute the schedule, as well as the lengths of the routes and the number of vehicles used. This paper gives a description of the solution methods of the above-mentioned participants. The second place method involves sequences of 22 low level heuristics: each of these heuristics is associated with a transition probability to move to another low level heuristic. A randomly drawn sequence of these heuristics is applied to an initial solution, after which the probabilities are updated depending on whether or not this sequence improved the objective value, hence increasing the chance of selecting the sequences that generate improved solutions. The third place method decomposes the problem into two independent parts: first, it schedules the delivery days for all requests using a genetic algorithm. Each schedule in the genetic algorithm is evaluated by estimating its cost using a deterministic routing algorithm that constructs feasible routes for each day. After spending 80 percent of time in this phase, the last 20 percent of the computation time is spent on Variable Neighborhood Descent to further improve the routes found by the deterministic routing algorithm. This article finishes with an in-depth comparison of the results of the two approaches.",
keywords = "Evolutionary computations, Inventory, Metaheuristics, Routing",
author = "Ahmed Kheiri and Dragomir, {Alina G.} and David Mueller and Joaquim Gromicho and Caroline Jagtenberg and {van Hoorn}, {Jelke J.}",
year = "2019",
doi = "10.1007/s13676-019-00143-8",
language = "English",
journal = "EURO Journal on Transportation and Logistics",
issn = "2192-4376",

}

Tackling a VRP challenge to redistribute scarce equipment within time windows using metaheuristic algorithms. / Kheiri, Ahmed; Dragomir, Alina G.; Mueller, David; Gromicho, Joaquim; Jagtenberg, Caroline; van Hoorn, Jelke J.

In: EURO Journal on Transportation and Logistics, 2019.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Tackling a VRP challenge to redistribute scarce equipment within time windows using metaheuristic algorithms

AU - Kheiri, Ahmed

AU - Dragomir, Alina G.

AU - Mueller, David

AU - Gromicho, Joaquim

AU - Jagtenberg, Caroline

AU - van Hoorn, Jelke J.

PY - 2019

Y1 - 2019

N2 - This paper reports on the results of the VeRoLog Solver Challenge 2016–2017: the third solver challenge facilitated by VeRoLog, the EURO Working Group on Vehicle Routing and Logistics Optimization. The authors are the winners of second and third places, combined with members of the challenge organizing committee. The problem central to the challenge was a rich VRP: expensive and, therefore, scarce equipment was to be redistributed over customer locations within time windows. The difficulty was in creating combinations of pickups and deliveries that reduce the amount of equipment needed to execute the schedule, as well as the lengths of the routes and the number of vehicles used. This paper gives a description of the solution methods of the above-mentioned participants. The second place method involves sequences of 22 low level heuristics: each of these heuristics is associated with a transition probability to move to another low level heuristic. A randomly drawn sequence of these heuristics is applied to an initial solution, after which the probabilities are updated depending on whether or not this sequence improved the objective value, hence increasing the chance of selecting the sequences that generate improved solutions. The third place method decomposes the problem into two independent parts: first, it schedules the delivery days for all requests using a genetic algorithm. Each schedule in the genetic algorithm is evaluated by estimating its cost using a deterministic routing algorithm that constructs feasible routes for each day. After spending 80 percent of time in this phase, the last 20 percent of the computation time is spent on Variable Neighborhood Descent to further improve the routes found by the deterministic routing algorithm. This article finishes with an in-depth comparison of the results of the two approaches.

AB - This paper reports on the results of the VeRoLog Solver Challenge 2016–2017: the third solver challenge facilitated by VeRoLog, the EURO Working Group on Vehicle Routing and Logistics Optimization. The authors are the winners of second and third places, combined with members of the challenge organizing committee. The problem central to the challenge was a rich VRP: expensive and, therefore, scarce equipment was to be redistributed over customer locations within time windows. The difficulty was in creating combinations of pickups and deliveries that reduce the amount of equipment needed to execute the schedule, as well as the lengths of the routes and the number of vehicles used. This paper gives a description of the solution methods of the above-mentioned participants. The second place method involves sequences of 22 low level heuristics: each of these heuristics is associated with a transition probability to move to another low level heuristic. A randomly drawn sequence of these heuristics is applied to an initial solution, after which the probabilities are updated depending on whether or not this sequence improved the objective value, hence increasing the chance of selecting the sequences that generate improved solutions. The third place method decomposes the problem into two independent parts: first, it schedules the delivery days for all requests using a genetic algorithm. Each schedule in the genetic algorithm is evaluated by estimating its cost using a deterministic routing algorithm that constructs feasible routes for each day. After spending 80 percent of time in this phase, the last 20 percent of the computation time is spent on Variable Neighborhood Descent to further improve the routes found by the deterministic routing algorithm. This article finishes with an in-depth comparison of the results of the two approaches.

KW - Evolutionary computations

KW - Inventory

KW - Metaheuristics

KW - Routing

UR - http://www.scopus.com/inward/record.url?scp=85065191272&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85065191272&partnerID=8YFLogxK

U2 - 10.1007/s13676-019-00143-8

DO - 10.1007/s13676-019-00143-8

M3 - Article

JO - EURO Journal on Transportation and Logistics

JF - EURO Journal on Transportation and Logistics

SN - 2192-4376

ER -