4 Presentations

• 
  01:30 PM - 01:55 PM

  On-Call/Casual Personnel Scheduling

  • Prakash Gawas, presenter, Polytechnique Montreal
  • Antoine Legrain, Polytechnique Montréal
  • Louis-Martin Rousseau, Polytechnique Montreal & CIRRELT

  We present a novel flexible on-call shift scheduling system with employee preferences that is responsible to interact with casual/on-call employees to schedule on-call shifts on short notice. The flexibility in the system also allows a senior employee to replace/bump a junior employee and change the current schedule under certain conditions. The objective in this dynamic problem is to minimize such schedule modifications while also minimizing the number of vacant shifts at the end of the planning process. An IP is formulated for the deterministic problem under complete information. We solve it approximately to gain insights that allow us to propose different policies for the dynamic problem.

• 
  01:55 PM - 02:20 PM

  Data Driven Synchronization Strategies Of A Bus Line In A Transit Network

  • Laura Kolcheva, presenter,
  • Antoine Legrain, Polytechnique Montréal
  • Martin Trépanier, Polytechnique Montréal, CIRRELT

  The waiting time of passengers at transfer stations is one of the most important criteria to measure the service quality of public bus transportation. Because of the stochastic nature of traffic, scheduled transfers cannot always occur. This research proposes an online control framework for a bus line using holding, skip-stop and speed change tactics. We build an arc-flow optimization model enumerating all possible tactics within a time horizon. The model minimizes total passenger travel times by improving, among others, transfer times and reducing deviations from the bus schedule. Decisions are based on real-time passenger flow data and travel times. This study is implemented in two steps: deterministic and stochastic The methodology was tested on a case-study of the bus system of the city of Laval, Canada. A simulation framework has been developed, integrating data on smart card transactions and bus locations, to verify the performance and results of the deterministic optimization model. Data generation in the simulation framework is improved using a training set. Different levels of uncertainty are tested on a training set and the resulting optimal parameters are applied to a validation set.

• 
  02:20 PM - 02:45 PM

  Solving the Online Stochastic Dial-a-ride Problem using Graphics Processing Unit

  • Ramesh Ramasamy Pandi, presenter, HEC Montreal
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
  • Yossiri Adulyasak, HEC Montréal
  • Louis-Martin Rousseau, Polytechnique Montréal

  Dial-a-ride problem (DARP) consists in designing routes and schedules to perform passenger transportation services while respecting a range of constraints. To efficiently operate dial-a-ride services, it is critical to design solution methods utilizing the available stochastic information online and leverage state-of-the-art computing technologies. We consider the online stochastic dial-a-ride problem with time windows in which the aim is to maximize the number of served customers. We present a solution framework that continuously generates new plans consistent with past decisions and anticipates future customer requests. Contrary to earlier studies, we introduce a new GPU-based optimization framework based on a large neighborhood search in which multiple cores are exploited to simultaneously evaluate future plans to assist in the decision-making. Simulations are conducted on various instances from the literature. Experimental results suggest that the proposed approach performs better than the existing approach since we evaluate a larger set of future plans using GPU for informed decision-making.

• 
  02:45 PM - 03:10 PM

  Online optimization of the dial-and-ride problem with the integral primal simplex

  • Elahe Amiri, presenter, Polytechnique Montréal
  • Antoine Legrain, Polytechnique Montréal

  Metropolitan areas seek to increase the use of ridesharing services to decrease congestion, parking issues and pollution. Several initiatives propose such services like UberPool. However, they rarely use advanced optimization methods due to complex implementation in practice. Developed algorithms for Dial-a-Ride Problem (DARP) in dynamic mode often try to batch requests to take advantage of the static optimization. They restart the optimization for each new batch without using previous solutions. our goal is to develop an algorithm for dynamic DARP that reuse previous computed results using the strengths of the integral primal simplex to expand the current routes with the new arrival requests.