A genetic algorithm for vehicle routing problems with temporal synchronization constraints

Stephan Hocke, Christina Gajewski and Mathias Kasper

No 2/2017, Discussion Papers from Technische Universität Dresden, "Friedrich List" Faculty of Transport and Traffic Sciences, Institute of Transport and Economics

Abstract: This paper presents a Genetic Algorithm for the Vehicle Routing and Scheduling Problem with time windows and temporal synchronization constraints. That means that as opposed to the usual procedure, in addition to the usual task covering, some vertices must be served by more than one vehicle at the same time. The chromosome coding used here is based on a proposed solution representation by Mankowska et al. [19]. The Genetic Algorithm is able to solve their instance types up to 20 vertices near to optimality. Even in greater instances with 100 vertices the solution quality of the Genetic Algorithm outperforms the Local Search presented by Mankowska et al. [19], however with losses in runtime. In order to get more comparable results, both solution approaches are evaluated at the well-known benchmark instances of Bredstrom and Ronnqvist [6]. This includes the presentation of a simple repair algorithm during the chromosome crossover based on an insertion heuristic in order to achieve the hard time window constraints of the benchmarks.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/233869/1/1757099182.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:zbw:tudiwv:22017

Access Statistics for this paper

More papers in Discussion Papers from Technische Universität Dresden, "Friedrich List" Faculty of Transport and Traffic Sciences, Institute of Transport and Economics Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().