Minimum cost VRP with time-dependent speed data and congestion charge

• The paper introduces a new heuristic algorithm to solve the cost optimization vehicle routing problem in a time-varying road network with congestion charge.
• The performance of the heuristic is tested by a specially designed benchmark dataset.
• The heuristic is also tested using real-world traffic data and road networks where a congestion charge scheme is in operation.

A heuristic algorithm, called LANCOST, is introduced for vehicle routing and scheduling problems to minimize the total travel cost, where the total travel cost includes fuel cost, driver cost and congestion charge. The fuel cost required is influenced by the speed. The speed for a vehicle to travel along any road in the network varies according to the time of travel. The variation in speed is caused by congestion which is greatest during morning and evening rush hours. If a vehicle enters the congestion charge zone at any time, a fixed charge is applied. A benchmark dataset is designed to test the algorithm. The algorithm is also used to schedule a fleet of delivery vehicles operating in the London area.