01155707

Component

The large-scale vehicle routing problem (VRP) with more than 1000 customers has received increasing attention for practicability. One of the efficient ways to solve this kind of combinatorial optimization problems is based on the cluster-first and route-second approach. For VRP with time windows (VRPTW) solved by this approach, however, temporal information is usually considered with vehicle routing but ignored in the process of clustering. Motivated by the theory of time geography, we propose a spatiotemporal partitioning approach for solving the large-scale VRPTW. We first present a spatiotemporal representation for the VRPTW, in which space and time are represented in the same coordination system. We then introduce a new approach that measures spatiotemporal distance between two customers, considering simultaneously the service time, travel time and time windows. A genetic algorithm is developed for k-medoid clustering of large-scale customers based on spatiotemporal distance. The numeric examples on extended Solomon’s benchmark problems show that, given the same cluster-first and route-second algorithm framework, the result from the spatiotemporal partitioning approach proposed in this paper is consistently better than that from models considering only spatial distance in the process of clustering.

01147878

10-1613

English

16p

2010

Transportation Research Board 89th Annual Meeting

DVD

Figures (5) ; References (31) ; Tables (3)

Advanced driver information systems; Genetic algorithms; Logistics; Physical distribution; Routing; Spatial analysis; Time windows; Travel time

Data and Information Technology; Freight Transportation

Transportation Research Board Annual Meeting 2010 Paper #10-1613

BTRIS, TRIS, TRB

Jan 25 2010 10:43AM