Optimization Online


Seamless Multimodal Transportation Scheduling

Arvind Raghunathan(raghunathan***at***merl.com)
David Bergman(david.bergman***at***uconn.edu)
John Hooker(jh38***at***andrew.cmu.edu)
Thiago Serra(tserra***at***merl.com)
Shingo Kobori(Kobori.Shingo***at***cj.MitsubishiElectric.co.jp)

Abstract: Ride-hailing services have expanded the role of shared mobility in passenger transportation systems, creating new markets and creative planning solutions for major urban centers. In this paper, we consider their use for last-mile passenger transportation in coordination with a mass transit service to provide a seamless multimodal transportation experience for the user. A system that provides passengers with predictable information on travel and waiting times in their commutes is immensely valuable. We envision that the passengers will inform the system in advance of their desired travel and arrival windows so that the system can jointly optimize the schedules of passengers. The problem we study balances minimizing travel time and the number of trips taken by the last-mile vehicles, so that long-term planning, maintenance, and environmental impact considerations can be taken into account. We focus our attention on the problem where the last-mile service aggregates passengers by destination. We show that this problem is NP-hard, and propose a decision diagram-based branch-and-price decomposition model that can solve instances of real-world size (10,000 passengers, 50 last-mile destinations, 600 last-mile vehicles) in time (∼ 1 minute) that is orders-of-magnitude faster than other methods appearing in the literature. Our experiments also indicate that single-destination last-mile service provides high-quality solutions to more general settings.

Keywords: last-mile; mass transit; scheduling; decision diagrams; branch and price.

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Transportation )

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

Citation: arxiv:1807.09676v1

Download: [PDF]

Entry Submitted: 07/26/2018
Entry Accepted: 07/26/2018
Entry Last Modified: 07/26/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