A genetic search algorithm for a vehicle routing problem with time windows

Abstract

This paper models a vehicle routing problem applied in Singapore transportation situation. It is close to the classical vehicle routing problem with time windows, but with two special characteristics. Firstly, the routes are designed for vehicles to serve the customers in a practical map modeled with a set of roads and junctions. Secondly, in order to manage the traffic conditions, the special Electronic Road Pricing (ERP) systems of Singapore applied in some roads are taken into consideration, which would affect the route cost for serving the customers. The overall objective of this problem is to obtain a set of routes with lowest cost to serve customers. This is a combinatorial optimization problem and difficult to find a good solution in a reasonable amount of time. To this end, a genetic search algorithm is developed to find a solution with high quality. An application example is demonstrated to verify its effectiveness. © 2010 IEEE.