Optimization Online


The Integrated Last-Mile Transportation Problem

Arvind U. Raghunathan(raghunathan***at***merl.com)
David Bergman(david.bergman***at***uconn.edu)
John Hooker(jh38***at***andrew.cmu.edu)
Thiago Serra(tserra***at***gmail.com)

Abstract: Last-mile transportation (LMT) refers to any service that moves passengers from a hub of mass transportation (MT), such as air, boat, bus, or train, to destinations, such as a home or an office. In this paper, we introduce the problem of scheduling passengers jointly on MT and LMT services, with passengers sharing a car, van, or autonomous pod of limited capacity for LMT. Passenger itineraries are determined so as to minimize total transit time for all passengers, with each passenger arriving at the destination within a specified time window. The transit time includes the time spent traveling through both services and, possibly, waiting time for transferring between the services. We provide an integer linear programming (ILP) formulation for this problem. Since the ILMTP is NP-hard and problem instances of practical size are often difficult to solve, we study a restricted version where MT trips are uniform, all passengers have time windows of a common size, and LMT vehicles visit one destination per trip. We prove that there is an optimal solution that sorts and groups passengers by their deadlines and, based on this result, we propose a constructive grouping heuristic and local search operators to generate high-quality solutions. The resulting groups are optimally scheduled in a few seconds using another ILP formulation. Numerical results indicate that the solutions obtained by this heuristic are often close to optimal and that warm-starting the ILP solver with such solutions decreases the overall computational times significantly.

Keywords: last-mile; mass transit; scheduling; integer programming

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: ICAPS 2018

Download: [PDF]

Entry Submitted: 06/21/2018
Entry Accepted: 06/22/2018
Entry Last Modified: 06/21/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society