Scheduling seminar

Download

schedulingseminar@rtime.felk.cvut.cz

November 2021

1 participants
2 discussions

Michel Gendreau (Polytech Montréal) | November 24 | Tabu search for the time-dependent vehicle routing problem with time windows on a road network
by Zdeněk Hanzálek 22 Nov '21

22 Nov '21

Dear scheduling researcher, We are delighted to announce the talk given by Michel Gendreau (Polytech Montréal). The title is "Tabu search for the time-dependent vehicle routing problem with time windows on a road network". The seminar will take place on Zoom on Wednesday, November 24 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/94687225692?pwd=SWVESXR6djcvWkpxeUc3a0xiLzVNQT09 Meeting ID: 946 8722 5692 Passcode: 557044 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Travel times inside cities often vary quite a lot during a day and significantly impact the duration of delivery routes. Some authors have proposed time-dependent (TD) variants of several vehicle routing problems (VRPs), including the VRP with time windows (VRPTW). In most papers, time-dependency is defined on customer-based graphs. Thus, a major impact of travel time variations is missed: in an urban environment, not only do travel times change, but also the paths used to travel from one customer to another. To address this issue, we work directly with the road network and consider travel time (or travel speed) variations on each road segment. We present a solution approach, based on tabu search, for a TDVRPTW in which travel speeds are associated with segments in the road network. Computational results on instances with up to 200 nodes and 580 arcs are reported and assessed. (Joint work with Maha Gmira, Andrea Lodi, and Jean-Yves Potvin). The next talk in our series will be given by Christoph Dürr (Sorbonne Uni)| December 8 | Three models for scheduling under explorable uncertainty For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Carlo Mannino (SINTEF & Oslo Uni.) | November 10 | Train Scheduling: Models, decomposition methods and practice.
by Zdeněk Hanzálek 08 Nov '21

08 Nov '21

Dear scheduling researcher, We are delighted to announce the talk given by Carlo Mannino (SINTEF & Oslo Uni.). The title is "Train Scheduling: Models, decomposition methods and practice". The seminar will take place on Zoom on Wednesday, November 10 at 14:00 UTC. Join Zoom Meeting https://cesnet.zoom.us/j/95159122899?pwd=R3IrUUNuUi9IV09Cejczb0FDS0loQT09 <https://cesnet.zoom.us/j/95159122899?pwd=R3IrUUNuUi9IV09Cejczb0FDS0loQT09> Meeting ID: 951 5912 2899 Passcode: 786508 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Train scheduling is one of the most critical planning tasks required to run a railway, with most rail operators and managers having large departments devoted to this task. Depending on the time scale, we have two main scheduling problems. At the strategic and tactical levels, the train timetabling problem consists in finding feasible, robust schedules that are usable for months or years into the future. At the operational level, we have the train re-scheduling problem, where one wants to schedule trains in real-time in order to tackle deviations from the original timetable, minimizing delays and knock-on effects. Both problems share a common core-model, which is a job-shop scheduling model with no-wait and blocking constraints. The core problem can be modeled as a disjunctive program. After an illustration of the train scheduling application, I will present a basic MILP formulation for the disjunctive program. It turns out, however, that even small to medium size real-life instances cannot be solved by simply instantiating this formulation and invoking a state-of-the-art MILP solver. Next, therefore, I will go through two recent reformulations, which allow us to significantly increase the size of tractable instances. The first is obtained from the classical Benders' reformulation by strengthening its standard constraints. The second is often referred to as "Logic Benders' Reformulation" and exploits a natural, spatial decomposition of the railway network. I will finally show the strong link between these reformulations. I will conclude the talk by presenting a practical application of the described approaches to a traffic management system controlling trains in the greater Oslo region network. The system is currently undergoing a field-test campaign at Oslo control center. The next talk in our series will be given by Michel Gendreau (Polytech Montréal) | November 24 | Tabu search for the time-dependent vehicle routing problem with time windows on a road network. For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0