A Genetic Algorithm in Combination with a Solution Archive for Solving the Generalized Vehicle Routing Problem with Stochastic Demands

Benjamin Biesinger (), Bin Hu () and Günther R. Raidl ()
Additional contact information
Benjamin Biesinger: Institute of Computer Graphics and Algorithms, TU Wien, 1040 Vienna, Austria; AIT Austrian Institute of Technology GmbH, Center for Mobility Systems, Dynamic Transportation Systems, 1210 Vienna, Austria
Bin Hu: Institute of Computer Graphics and Algorithms, TU Wien, 1040 Vienna, Austria; AIT Austrian Institute of Technology GmbH, Center for Mobility Systems, Dynamic Transportation Systems, 1210 Vienna, Austria
Günther R. Raidl: Institute of Computer Graphics and Algorithms, TU Wien, 1040 Vienna, Austria

Transportation Science, 2018, vol. 52, issue 3, 673-690

Abstract: This work presents a steady-state genetic algorithm enhanced by a complete trie-based solution archive for solving the generalized vehicle routing problem with stochastic demands using a preventive restocking strategy. As the necessary dynamic programming algorithm for the solution evaluation is very time consuming, considered candidate solutions are stored in the solution archive. It acts as complete memory of the search history, avoids reevaluations of duplicate solution candidates, and is able to efficiently transform them into guaranteed new ones. This increases the diversity of the population and reduces the risk of premature convergence. Similar to a branch-and-bound algorithm, the tree structure of the solution archive is further exploited to compute lower bounds on the nodes to cut off parts of the solution space that evidently do not contain good solutions. Since in each iteration a not yet considered solution candidate is generated and completeness can be efficiently checked, the overall method is in principle an exact enumeration algorithm, which leads to guaranteed optimal solutions for smaller instances. Computational results of this algorithm show the superiority over the so far state-of-the-art metaheuristic and also prove its effectiveness on the nongeneralized version of this problem.

Keywords: stochastic vehicle routing problem; generalized vehicle routing problem; genetic algorithm; complete solution archive (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0778 (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:inm:ortrsc:v:52:y:2018:i:3:p:673-690

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().