10h30 - 11h30
A Column Generation with Constraint Programming Scheme that Considers Robust Optimization, Simulation, and Local Search Heuristics to Solve Several Versions of a Real Technician-Dispatching Problem
In this tutorial, I will show a family of models and solution methods we have been working on the last years, to solve a real application of a technician dispatching problem from one year data of a large company providing repair service of office machines in Santiago-Chile. Crucial in the problem is to incorporate clients with different priorities, phenomenon that is modeled with the soft time windows. It is worth to mention that different conditions generate different solution schemes. We started with the static deterministic routing of technicians for daily planning, in which we assume that service requests are well known in advance; for this case, we propose a branch and price scheme to solve a vehicle routing problem with soft time windows, in which the subproblems are efficiently solved by means of a constraint programming model, which allows the implementation of a generic branching scheme to explore efficiently the different nodes in the tree. We then decide to add uncertainty in service times formulating a robust counterpart of the previous problem, ending up with a similar formulation and solution method, but now providing safer solutions in the sense of avoiding unnecessary delays due to stochasticity in service times. The third step was the development of an annual planning scheme, in which we combine simulation with the optimization scheme for the daily operation, to design the fleet requirements over a whole year of operation. Finally, we show the formulation of the dynamic version of the problem, in which decisions are made in real-time while clients appear dynamically into the system; the model is based on dynamic column generation, including idle points together with covering rules to ensure adequate level of service to clients, and efficient local search heuristics to dynamically generate new columns to be added to the model. All versions (deterministic routing, robust counterpart, dynamic routing and fleet design) are tested with real data, showing interesting and intuitive results for various scenarios of high, medium and low demand levels under various configurations and uncertainty in demand and service times.
Coauthors: Paulina Briceño, Michel Gendreau, Daniel Leng, Fernando Ordoñez, José Rojas, Louis Martin Rousseau, Sebastián Souyris, Andrés Weintraub.