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

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 ...

• Publication year

  2018

• Venue

  Transportation Science

• Publication date

  2018-02-15

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1287/trsc.2017.0778
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Vehicle Routing Problem with Stochastic Demand

  2017cited by this paper
• An Integer L-shaped Method for the Generalized Vehicle Routing Problem with Stochastic Demands

  2016cited by this paper
• Models and algorithms for competitive facility location problems with different customer behavior

  2016cited by this paper
• A Glowworm Swarm Optimization algorithm for the Vehicle Routing Problem with Stochastic Demands

  2016cited by this paper
• A Memetic Differential Evolution Algorithm for the Vehicle Routing Problem with Stochastic Demands

  2015cited by this paper
• A hybrid genetic algorithm with solution archive for the discrete (r|p)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$

  2015cited by this paper
• A Variable Neighborhood Search for the Generalized Vehicle Routing Problem with Stochastic Demands

  2015cited by this paper
• An Evolutionary Algorithm for the Leader-Follower Facility Location Problem with Proportional Customer Behavior

  2014cited by this paper
• Partial-route inequalities for the multi-vehicle routing problem with stochastic demands

  2014influential reference
• Exact and heuristic algorithms for solving the generalized vehicle routing problem with flexible fleet size

  2014influential reference
• A Variable Neighborhood Search Approach for Solving the Generalized Vehicle Routing Problem

  2014cited by this paper
• A Hybrid Clonal Selection Algorithm for the Vehicle Routing Problem with Stochastic Demands

  2014cited by this paper
• An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size

  2014cited by this paper
• Combinatorial expanding neighborhood topology particle swarm optimization for the vehicle routing problem with stochastic demands

  2013cited by this paper
• Particle Swarm Optimization for the Vehicle Routing Problem with Stochastic Demands

  2013cited by this paper
• Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand

  2012cited by this paper
• An evolutionary algorithm with solution archives and bounding extension for the generalized minimum spanning tree problem

  2012cited by this paper
• A Memetic Algorithm and a Solution Archive for the Rooted Delay-Constrained Minimum Spanning Tree Problem

  2011cited by this paper
• An Evolutionary Algorithm with Solution Archive for the Generalized Minimum Spanning Tree Problem

  2011cited by this paper
• Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem

  2011influential reference
• A Hybrid Monte Carlo Local Branching Algorithm for the Single Vehicle Routing Problem with Stochastic Demands

  2010cited by this paper
• Enhancing Genetic Algorithms by a Trie-Based Complete Solution Archive

  2010cited by this paper
• An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands

  2010cited by this paper
• A Genetic Algorithm for Solving the Generalized Vehicle Routing Problem

  2010cited by this paper
• A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands

  2009cited by this paper
• A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands

  2007cited by this paper
• Dynamic And Stochastic Vehicle Routing In Practice

  2007cited by this paper
• Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

  2005influential reference
• Integer Linear Programming Formulation of the Generalized Vehicle Routing Problem

  2003cited by this paper
• An Integer L-Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands

  2002cited by this paper
• An efficient transformation of the generalized vehicle routing problem

  2000cited by this paper
• Stochastic Vehicle Routing Problem with Restocking

  2000influential reference
• New optimality cuts for a single‐vehicle stochastic routing problem

  1999cited by this paper
• Variable neighborhood search: Principles and applications

  1998cited by this paper
• Solving Stochastic Routing Problems with the Integer L-Shaped Method

  1998cited by this paper
• Duplicate genotypes in a genetic algorithm

  1998cited by this paper
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem

  1997cited by this paper
• A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers

  1996cited by this paper
• An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers

  1995cited by this paper
• String Searching Algorithms

  1994cited by this paper
• Maintaining Diversity in Genetic Search

  1984cited by this paper

• Collaborative multicenter delivery and pickup network design with transportation resource configuration and alliance synergy service

  2026cites this paper
• Multi-Day Travel Route Planning Using the Firefly Algorithm for Distance and Transportation Cost Efficiency

  2025cites this paper
• Vehicle Routing Problems: From Deterministic Models to Stochastic Solutions

  2025cites this paper
• Stochastic Multi-Objective Multi-Trip AMR Routing Problem with Time Windows

  2024cites this paper
• A Novel Self-Healing Genetic Algorithm for Optimizing Single Objective Flow Shop Scheduling Problem

  2024cites this paper
• The multidepot vehicle routing problem with intelligent recycling prices and transportation resource sharing

  2024cites this paper
• Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm

  2024cites this paper
• Truck-drone routing problem with stochastic demand

  2024cites this paper
• An Integer L-shaped algorithm for vehicle routing problem with simultaneous delivery and stochastic pickup

  2023cites this paper
• Stochastic Multi-Objective Vehicle Routing Model in Green Environment With Customer Satisfaction

  2023cites this paper
• Improving the efficiency of patient diagnostic specimen collection with the aid of a multi-modal routing algorithm

  2023cites this paper
• Clustering retail stores for inventory transshipment

  2023cites this paper
• A vehicle routing problem with multiple service agreements

  2023cites this paper
• Generalized vehicle routing problem: Contemporary trends and research directions

  2023cites this paper
• Hybrid partheno-genetic algorithm for multi-depot perishable food delivery problem with mixed time windows

  2022influential citation
• Offline approximate value iteration for dynamic solutions to the multivehicle routing problem with stochastic demand

  2022cites this paper
• The role of artificial intelligence in supply chain management: mapping the territory

  2022cites this paper
• Optimization of Humanitarian Aid Distribution in Case of an Earthquake and Tsunami in the City of Iquique, Chile

  2022cites this paper
• Modified A* Algorithm integrated with ant colony optimization for multi-objective route-finding; case study: Yazd

  2021cites this paper
• Service-oriented global optimization integrating maintenance grouping and technician routing for multi-location multi-unit production systems

  2021cites this paper
• THE VEHICLE ROUTING PROBLEM WITH STOCHASTIC DEMANDS IN AN URBAN AREA – A CASE STUDY

  2020cites this paper
• Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands

  2020cites this paper
• Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis

  2019cites this paper
• Stokastik Talepli Araç Rotalama Problemi İçin Literatür Taraması

  2019cites this paper
• An improved genetic algorithm for numerical function optimization

  2018cites this paper