TR2018-084

The Integrated Last-Mile Transportation Problem (ILMTP)


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.

 

  • Related News & Events

    •  NEWS   Best doctoral dissertation award received by Visiting Research Scientist Thiago Serra
      Date: June 4, 2018
      Where: Pittsburgh, Pennsylvania
      MERL Contact: Arvind Raghunathan
      Research Area: Optimization
      Brief
      • Thiago Serra, currently a Visiting Research Scientist in the Data Analytics group, has been awarded the Gerald L. Thompson Doctoral Dissertation Award in Management Science from the Tepper School of Business, Carnegie Mellon University. This is awarded each year to honor an outstanding doctoral dissertation involving theoretical, computational and applied contributions in the area of Management Science. One of the thesis chapters, "The Integrated Last-Mile Transportation Problem" was work performed at MERL in conjunction with Arvind Raghunathan during a summer internship. This work resulted in a patent application and will be presented at the 2018 International Conference on Automated Planning and Scheduling (ICAPS).
    •