Spatiotemporal Partitioning Approach for Large-Scale Vehicle Routing Problem with Time Windows

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.

Language

  • English

Media Info

  • Media Type: DVD
  • Features: Figures; References; Tables;
  • Pagination: 16p
  • Monograph Title: TRB 89th Annual Meeting Compendium of Papers DVD

Subject/Index Terms

Filing Info

  • Accession Number: 01155707
  • Record Type: Publication
  • Report/Paper Numbers: 10-1613
  • Files: BTRIS, TRIS, TRB
  • Created Date: Jan 25 2010 10:43AM