4 Presentations

• 
  03:30 PM - 03:55 PM

  Joint Rolling Stock and Crew Scheduling with Multi-train Composition in Urban Rail Networks

  • Entai Wang, presenter, HEC Montreal
  • Lixing Yang, Beijing Jiaotong University
  • Yossiri Adulyasak, HEC Montreal
  • Cordeau Jean-François, HEC Montreal, Department of Logistics and Operations Management
  • Ziyou Gao, Beijing Jiaotong University

  Rolling stock scheduling and crew scheduling are two fundamental problems that arise in the planning of urban rail operations and that are especially important in the case of flexible operations in real-world networks. These problems are often solved separately and sequentially in different planning stages, resulting in limited options to adjust crew schedules after rolling stock decisions have been made. To better adjust these two decision-making processes and achieve better solutions, this paper studies a joint rolling stock and crew scheduling problem in urban rail networks. A novel optimization model is formulated with the aim of reducing the operational cost of rolling stock units and crew members. In addition, the multi-train composition mode is considered to adequately match different frequency requirements and rolling stock transport capacities. To solve the model, a customized branch-and-price-and-cut solution algorithm is proposed to find the optimal schedule schemes, in which Benders decomposition is used to solve the linear programming relaxation of the path-based reformulation. Two customized column generation methods with label correcting are embedded to solve the master problem and sub-problem for generating paths (columns) corresponding to rolling stock units and crew groups, respectively. Finally, a branch-and-bound procedure with several acceleration techniques is proposed to find integer solutions. To demonstrate the computational performance and the robustness of the proposed approaches, a series of numerical experiments are performed on real-world instances of the Beijing urban rail network under different settings. The computational results confirm the high efficiency of the solution methodology and the benefits of the flexible operation schemes based on the solutions found by the proposed methods.

• 
  03:55 PM - 04:20 PM

  Online Resource Allocation Problem with Departures

  • Yusuf Amidu, presenter, Khalifa University

  In this paper we propose a novel primal-dual algorithm for the following online resource allocation problem. Requests arrive over time to a set of resources and upon arrival, the time a request may occupy a resource becomes known. We assume that the duration of stay of a request is deterministic, may depend on the resource and that resources may have different capacities. The goal is to decide whether to accept/reject a request upon arrival and to which resource to allocate it such that the reward obtained over a time T is maximized. We show that the proposed primal-dual algorithm achieves a competitive ratio of O(R/r) , where R is the maximum reward and r is the minimum reward that can be obtained. Through numerical experiments, we show that the primal-dual algorithm has lower computation times than a recent algorithm proposed in the literature, while having a similar performance in practical instances.

• 
  04:20 PM - 04:45 PM

  Efficient decomposition methods for Large Scale, Multi-Period Log Truck Routing and Scheduling:Application to Canadian Forestry

  • Abdelhakim Abdellaoui, presenter, Polytechnique Montréal
  • El Hallaoui Issmail, GERAD & Polymtl
  • Loubna Benabbou, UQAR
  • François Aubé, CanmetÉnergie
  • Mouloud Amazouz, Natural Resources Canada (NRCan)

  This work addresses the complex multi-period log-truck routing and scheduling problem encountered in the forest industry. We propose an improved mathematical formulation and decomposition approaches to efficiently solve large-scale instances of this problem. Given that timber harvesting operations in Canada extend far from processing facilities, efficient transportation is essential for economic viability and environmental sustainability.

  Our research analyzes business rules within the forestry sector to develop a generalized framework for routing network design. We then formulate a comprehensive MILP, incorporating spatial and temporal constraints such as time windows, truck capacities, mill and harvest site accessibility, multi-period replenishment, and other resource constraints. To tackle the problem’s combinatorial complexity, we apply a preprocessing strategy to reduce the search space. We further develop primal decomposition methods, introducing a new Price-and-Branch approach and an adapted Relax-and-Fix strategy. Our computational experiments, conducted using historical data from a Canadian forest company, demonstrate the effectiveness of our approach, achieving near-optimal solutions (within a 2% gap of the lower bound) in less than 10 minutes for the weekly routing and scheduling problem. This research contributes to ongoing efforts to enhance operational efficiency, reduce environmental impact, and maintain the competitiveness of Canada’s forestry sector.

• 
  04:45 PM - 05:10 PM

  The vehicle routing problem with driver scheduling

  • Razieh Mousavi, presenter, Université Laval
  • Jean-François Côté, Université Laval
  • Maryam Darvish, Université Laval

  This talk addresses the Vehicle Routing Problem with Driver Scheduling, which integrates the Vehicle Routing Problem with Time Windows and Shift Scheduling Problem. The problem becomes more complex when vehicle routing and shift scheduling are solved together, as both aspects need to be optimized simultaneously. We also consider availability for each driver, which further complicates the problem, as the solution must optimize routes while aligning them with driver-specific availability. Considering drivers' availability in vehicle scheduling and routing is essential for improving driver satisfaction and ensuring punctuality in road freight transport. The objective is to minimize total costs, including travel costs, shift costs, and the costs of outsourcing unassigned customers to a Third-Party Logistics (3PL) provider. This talk proposes the mathematical formulation of the problem and a heuristic approach based on the Iterated Local Search (ILS) algorithm.