The Dial-a-Ride Problem (DARP) involves designing vehicle routes and schedules for customers with specified pickup and delivery requests between their origins and destinations. The objective is to minimize the cost of vehicle routes while adhering to constraints such as vehicle capacity, time windows, and maximum ride time. This paper proposes a branch-and-price-and-cut (B&P&C) algorithm to address a variant of DARP where both customers and the vehicle fleet are heterogeneous, alongside practical constraints like budget, breaks with different configurations, and maximum run duration. The algorithm employs a column generation approach at each node in the branching tree, decomposing the problem into a master problem and subproblems. Exact and heuristic versions of the labeling algorithm are developed to efficiently handle these subproblems. The effectiveness of the algorithm is assessed through a real-world case study involving 849 heterogeneous passengers and over 70 available vehicles, represented as contracts with varying cost structures. Notably, this instance marks the largest problem size addressed using an exact B&P&C algorithm to our knowledge. Results demonstrate that the proposed algorithm achieves highly competitive solution quality.

Governments globally are incentivising zero-emission vehicle sales and charging infrastructure development to cut transportation emissions. These incentives, along with higher market availability, lower fuel cost and extended battery range, make electric coaches viable for intercity public transportation. In collaboration with Ember Core Ltd., the first intercity operator in the United Kingdom to use an all-electric fleet, we have conducted research on maximising the utility of their electric coaches and charging infrastructure while ensuring that schedules fulfil the operational restrictions of intercity electric transportation. As a result, we introduce the Intercity Electric Coach Scheduling Problem along with a column generation algorithm that uses a variable fixing heuristic to find integer solutions. The algorithm is embedded in an iterative framework to generate schedules for a long planning horizon. It provides quality schedules that successfully meet Ember’s real-world requirements. In the forthcoming presentation, we will discuss the challenges of sparse charging networks, regular maintenance scheduling and overnight timetables that make intercity electric coach scheduling a difficult problem to solve. However, we also explain how we can exploit these characteristics and provide a comprehensive analysis of the algorithm’s solution quality and performance.

We present a unifying framework for Selective Routing Problems (SRPs) through a systematic analysis. The common goal in SRPs is to determine an optimal vehicle route to serve a subset of vertices while covering another subset. They arise in diverse fields such as logistics, public health, disaster response, and urban development. To establish a unifying framework for different but related problems, we associate the notion of service with coverage and argue that routing is a tool of service. We classify SRPs according to their selectiveness degree and emphasize the breadth and depth of this problem in terms of its characteristics. This SRP framework helps us identify research gaps as well as potential future research areas. We present a generic mathematical model, use it to describe the connections among these problems and identify some identical problems presented under different names.