An Adaptive Guidance Approach for the Heuristic Solution of a Multi-Trip Vehicle Routing Problem

Maria Battarra, Michele Monaci, Daniele Vigo

Research output: Contribution to journalArticle

48 Citations (Scopus)

Abstract

One of the most important problems in combinatorial optimization is the well-known vehicle routing problem (VRP), which calls for the determination of the optimal routes to be performed by a fleet of vehicles to serve a given set of customers. Recently, there has been an increasing interest towards extensions of VRP arising from real-world applications. In this paper we consider a variant in which time windows for service at the customers are given, and vehicles may perform more than one route within a working shift. We call the resulting problem the minimum multiple trip VRP (MMTVRP), where a “multiple trip” is a sequence of routes corresponding to a working shift for a vehicle. The problem objective is to minimize the overall number of the multiple trips (hence the size of the required fleet), breaking ties in favor of the minimum routing cost.

We propose an iterative solution approach based on the decomposition of the problem into simpler ones, each solved by specific heuristics that are suitably combined to produce feasible MMTVRP solutions. An adaptive guidance mechanism is used to guide the heuristics to possibly improve the current solution. Computational experiments have been performed on a set of real-world instances arising from a multi-regional scale distribution problem. The obtained results show that the proposed adaptive guidance mechanism is considerably effective, being able to reduce the overall number of required vehicles within a limited computing time.
LanguageEnglish
Pages3041-3050
JournalComputers and Operations Research
Volume36
Issue number11
DOIs
StatusE-pub ahead of print - 25 Feb 2009

Fingerprint

Vehicle routing
Vehicle Routing Problem
Guidance
Heuristics
Customers
Combinatorial optimization
Time Windows
Combinatorial Optimization
Iterative Solution
Tie
Real-world Applications
Computational Experiments
Decomposition
Routing
Vehicle routing problem
Minimise
Decompose
Computing
Costs
Experiments

Cite this

An Adaptive Guidance Approach for the Heuristic Solution of a Multi-Trip Vehicle Routing Problem. / Battarra, Maria; Monaci, Michele; Vigo, Daniele.

In: Computers and Operations Research, Vol. 36, No. 11, 25.02.2009, p. 3041-3050.

Research output: Contribution to journalArticle

@article{0261cbcc56444e64beca732e092d046e,
title = "An Adaptive Guidance Approach for the Heuristic Solution of a Multi-Trip Vehicle Routing Problem",
abstract = "One of the most important problems in combinatorial optimization is the well-known vehicle routing problem (VRP), which calls for the determination of the optimal routes to be performed by a fleet of vehicles to serve a given set of customers. Recently, there has been an increasing interest towards extensions of VRP arising from real-world applications. In this paper we consider a variant in which time windows for service at the customers are given, and vehicles may perform more than one route within a working shift. We call the resulting problem the minimum multiple trip VRP (MMTVRP), where a “multiple trip” is a sequence of routes corresponding to a working shift for a vehicle. The problem objective is to minimize the overall number of the multiple trips (hence the size of the required fleet), breaking ties in favor of the minimum routing cost.We propose an iterative solution approach based on the decomposition of the problem into simpler ones, each solved by specific heuristics that are suitably combined to produce feasible MMTVRP solutions. An adaptive guidance mechanism is used to guide the heuristics to possibly improve the current solution. Computational experiments have been performed on a set of real-world instances arising from a multi-regional scale distribution problem. The obtained results show that the proposed adaptive guidance mechanism is considerably effective, being able to reduce the overall number of required vehicles within a limited computing time.",
author = "Maria Battarra and Michele Monaci and Daniele Vigo",
year = "2009",
month = "2",
day = "25",
doi = "10.1016/j.cor.2009.02.008",
language = "English",
volume = "36",
pages = "3041--3050",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier",
number = "11",

}

TY - JOUR

T1 - An Adaptive Guidance Approach for the Heuristic Solution of a Multi-Trip Vehicle Routing Problem

AU - Battarra, Maria

AU - Monaci, Michele

AU - Vigo, Daniele

PY - 2009/2/25

Y1 - 2009/2/25

N2 - One of the most important problems in combinatorial optimization is the well-known vehicle routing problem (VRP), which calls for the determination of the optimal routes to be performed by a fleet of vehicles to serve a given set of customers. Recently, there has been an increasing interest towards extensions of VRP arising from real-world applications. In this paper we consider a variant in which time windows for service at the customers are given, and vehicles may perform more than one route within a working shift. We call the resulting problem the minimum multiple trip VRP (MMTVRP), where a “multiple trip” is a sequence of routes corresponding to a working shift for a vehicle. The problem objective is to minimize the overall number of the multiple trips (hence the size of the required fleet), breaking ties in favor of the minimum routing cost.We propose an iterative solution approach based on the decomposition of the problem into simpler ones, each solved by specific heuristics that are suitably combined to produce feasible MMTVRP solutions. An adaptive guidance mechanism is used to guide the heuristics to possibly improve the current solution. Computational experiments have been performed on a set of real-world instances arising from a multi-regional scale distribution problem. The obtained results show that the proposed adaptive guidance mechanism is considerably effective, being able to reduce the overall number of required vehicles within a limited computing time.

AB - One of the most important problems in combinatorial optimization is the well-known vehicle routing problem (VRP), which calls for the determination of the optimal routes to be performed by a fleet of vehicles to serve a given set of customers. Recently, there has been an increasing interest towards extensions of VRP arising from real-world applications. In this paper we consider a variant in which time windows for service at the customers are given, and vehicles may perform more than one route within a working shift. We call the resulting problem the minimum multiple trip VRP (MMTVRP), where a “multiple trip” is a sequence of routes corresponding to a working shift for a vehicle. The problem objective is to minimize the overall number of the multiple trips (hence the size of the required fleet), breaking ties in favor of the minimum routing cost.We propose an iterative solution approach based on the decomposition of the problem into simpler ones, each solved by specific heuristics that are suitably combined to produce feasible MMTVRP solutions. An adaptive guidance mechanism is used to guide the heuristics to possibly improve the current solution. Computational experiments have been performed on a set of real-world instances arising from a multi-regional scale distribution problem. The obtained results show that the proposed adaptive guidance mechanism is considerably effective, being able to reduce the overall number of required vehicles within a limited computing time.

U2 - 10.1016/j.cor.2009.02.008

DO - 10.1016/j.cor.2009.02.008

M3 - Article

VL - 36

SP - 3041

EP - 3050

JO - Computers and Operations Research

T2 - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 11

ER -