Titel
A template-based adaptive large neighborhood search for the consistent vehicle routing problem
Abstract
The importance of customer satisfaction was identified by many industries as a key factor of competitive advantage. So, for companies in the small package shipping industry it can be reasonable to increase the service quality even at the expense of transportation cost in order to gain customer loyalty. These companies noticed that customer satisfaction can be increased by providing consistent service in the form of visiting customers with the same driver at approximately the same time of the day over a certain time period. Motivated by this real world problem, the consistent vehicle routing problem (ConVRP) combines traditional vehicle routing constraints with the requirements for service consistency. This paper presents a fast solution method called template based adaptive large neighborhood search for the described problem. Compared to state-of-the-art heuristics, the developed algorithm is highly competitive on the available benchmark instances. Additionally, new test instances are provided. These seem to be more challenging due to the variation of different model parameters and consequently help to identify interesting effects. Finally, a relaxed variant of the original ConVRP is presented. In this variant, the departure times from the depot can be delayed to adjust the service times of the customers. Experiments show that allowing later departure times considerably improves the solution quality under tight consistency requirements. (available online 1 Oct 2013)
Stichwort
vehicle routing, periodic distribution problems, large neighborhood search, metaheuristics
Objekt-Typ
Sprache
Englisch [eng]
Persistent identifier
https://phaidra.univie.ac.at/o:397974
Erschienen in
Titel
NETWORKS
Band
63
Ausgabe
1
Seitenanfang
60
Seitenende
81
Verlag
Wiley-Blackwell
Projektnummer
T514-N13 – Austrian Science Fund (FWF)
Datum der Annahme zur Veröffentlichung
2014
Zugänglichkeit

Herunterladen

Universität Wien | Universitätsring 1 | 1010 Wien | T +43-1-4277-0