Scenario-Guided Large Neighborhood Search for Integrated Transportation of Goods and Passengers via Ferries

In cities with bodies of water, traffic often faces detours. Although passenger ferry systems mitigate this, last-mile delivery of goods still depends on congested road networks. We propose an integrated transportation system for freight and passengers that utilizes ferries. The ferries dock at shoreline stations, serving as delivery points and temporary storage for goods. As goods are dropped off during the day, more capacity becomes available for passenger transportation. Although demand fluctuates daily, the ferry service must follow a fixed schedule because, otherwise, it will not be attractive to passengers. We formulate this as a capacitated vehicle routing problem with multiple visits, dynamic demand, and stochastic objective function. We propose a novel scenario-guided large neighborhood search that evaluates solutions on a set of scenarios and leverages insights from the demand data and evaluation for tailored search operators. The tailored operators substantially improve the solution quality, even when relying on expected values. Evaluation of scenarios adds to the solution quality, but only if it does not come as a stand-alone but is combined with the tailored operators. Our results further show that with the right strategy, combining freight and passenger transportation does not come at the expense of passenger service. Funding: M. W. Ulmer and C. Ackva received financial support from Deutsche Forschungsgemeinschaft (Emmy Noether Programme, project 444657906). Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0983 .