2007•Unpublished venueRequires access

Efficient evolutionary algorithm for the vehicle routing problem with time windows: edge assembly crossover for the VRPTW

Yuichi Nagata

Abstract

We propose an evolutionary algorithm (EA) for the vehicle routing problem with time windows (VRPTW). In particular, a crossover operator suitable for solving the VRPTW are presented. The proposed crossover is designed by extending edge assembly crossover (EAX) which was originally designed for the traveling salesman problem (TSP). Moreover, we propose an efficient modification procedure to eliminate violations of the capacity constraints and the time window constraints because intermediate solutions generated by EAX violate these constraints. The EA is composed of EAX, the modification procedure and a very simple local search. The EA is applied to the well-known Gering and Homberger benchmarks for the VRPTW. The EA finds new best-known solutions in 119 of the 180 instances (200 - 600 customer benchmarks).

About this research paper

What this paper is about

Why it matters

OpenAlex reports 14 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Key concepts: Crossover, Vehicle routing problem, Enhanced Data Rates for GSM Evolution, Travelling salesman problem, Mathematical optimization, Operator (biology), Routing (electronic design automation), Simple (philosophy)