𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Edge assembly-based memetic algorithm for the capacitated vehicle routing problem

✍ Scribed by Yuichi Nagata; Olli Bräysy

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
200 KB
Volume
54
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Vehicle routing problems are at the heart of most decision support systems for real‐life distribution problems. In vehicle routing problem a set of routes must be determined at lowest total cost for a number of resources (i.e., fleet of vehicles) located at one or several points (e.g., depots, warehouses) to efficiently service a number of demand or supply points. In this article a new memetic algorithm is suggested for the standard capacitated vehicle routing problem. The proposed algorithm combines the edge assembly (EAX) crossover with well‐known local searches and allows for infeasible solutions with respect to capacity and route duration constraints after invoking the crossover. To address the constraint violation, an efficient modification algorithm is also suggested. Experimental tests on 47 standard benchmarks demonstrate that the suggested method is robust and competitive, finding new best‐known solution to 20 well‐studied instances and repeating the existing best‐known solution for 24 problems in a reasonable computing time. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

📜 SIMILAR VOLUMES

Two exact algorithms for the vehicle rou
Two exact algorithms for the vehicle routing problem on trees
✍ Pontien Mbaraga; André Langevin; Gilbert Laporte 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time-constrained vehicle routing problems. One of the exact algorithms is based on the computation of bin packing lower bounds. The othe

A branch-and-price-based large neighborh
A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows
✍ Eric Prescott-Gagnon; Guy Desaulniers; Louis-Martin Rousseau 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB

## Abstract Given a fleet of vehicles assigned to a single depot, the vehicle routing problem with time windows (VRPTW) consists of determining a set of feasible vehicle routes to deliver goods to a set of customers while minimizing, first, the number of vehicles used and, second, total distance tr