Vehicle routing with hard time windows and stochastic service times: exact solution methods for two models
Michel Gendreau, MAGI and CIRRELT, École Polytechnique Montreal, Canada
We consider a vehicle routing problem typically encountered in the scheduling of repairmen, in which one must deal with deterministic travel times, stochastic service times, hard time windows, and no capacity constraints. We first present a chance-constrained formulation, which has an obvious interpretation. We also propose a second formulation as a two-stage stochastic program with recourse, in which different recourse strategies can be considered. Exact solution procedures based on column generation and branch-and-price are presented for both models. These procedures can solve instances with up to 50 customers.
Joint work with Fausto Errico, Guy Desaulniers, Walter Rei, and Louis-Martin Rousseau.
A branch-and-price algorithm for the network pricing problem with connected toll arcs
Martine Labbé, Département d'Informatique, Université Libre de Bruxelles
We propose a branch-and-price approach to solve a pricing problem on a network with connected toll arcs. The model is obtained with a Dantzig-Wolfe reformulation, and a column generation algorithm is used to solve the linear relaxation. Various techniques have been considered to improve the efficiency of the solving algorithm, such as stabilisation and different branching strategies. Numerical results show the effectiveness of this approach.
This is a joint work with Bernard Fortz and Alessia Violin.
Retail store scheduling for profit
Louis-Martin Rousseau, MAGI and CIRRELT, École Polytechnique Montreal, Canada
In spite of its tremendous economic significance, the problem of sales staff schedule optimization for retail stores has received relatively scant attention. Current approaches typically attempt to minimize payroll costs by closely fitting a staffing curve derived from exogenous sales forecasts, oblivious to the ability of additional staff to (sometimes) positively impact sales. In contrast, this paper frames the retail scheduling problem in terms of operating profit maximization, explicitly recognizing the dual role of sales employees as sources of revenues as well as generators of operating costs. We introduce a flexible stochastic model of retail store sales, estimated from store-specific historical data, that can account for the impact of all known sales drivers, including the number of scheduled staff, and provide an accurate sales forecast at a high intra-day resolution. We also present solution techniques based on mixed-integer (MIP) and constraint programming (CP) to efficiently solve the complex mixed integer non-linear scheduling (MINLP) problem with a profit-maximization objective. The proposed approach allows solving full weekly schedules to optimality, or near-optimality with a very small gap. On a case-study with a medium-sized retail chain, this integrated forecasting–scheduling methodology yields significant projected net profit increases on the order of 2–3% compared to baseline schedules.
Joint work with Nicolas Chapados, Marc Joliveau, Pierre L’Ecuyer.
Hybrid approach for a multiple trip vehicle routing problem with depot queuing and time dependent travel times
Cristián E. Cortés, Universidad de Chile
In this work, we develop a hybrid model for solving the fleet design and vehicle dispatching in the context of a real problem of product delivery associated with the e-commerce industry. The proposed model uses a heuristic method designed to create a pool of feasible single trip routes that feeds a more complex set partitioning model, which selects the best set of routes in order to minimize the distance traveled considering tight hard time windows for delivery at the clients locations, and the operational constraints arising from the depot queue appearing when two or more vehicles (normally, trucks) need to be loaded simultaneously for their next trip. Simulated data from an existing e-commerce firm is used to test the methodology proposed, including formulation and solution algorithm. Promising preliminary results are obtained from simulated data of a real case scenario.
Joint work with Pablo Rey and Pablo Saintard.
Stackelberg security games
Fernando Ordóñez, Universidad de Chile
Stackelberg games model a strategic interaction between players where one participant is able to commit to a strategy first knowing that the rest will respond in an optimal manner. Recent work has focused on Stackelberg games in security domains, referred to as Stackelberg Security Games (SSG), where a defender protects critical infrastructure and acts first in the presence of strategic attackers that take the defender action into account in deciding their attack.
In this talk I will review the different models and solution algorithms for SSG that address issues such as scalability, lack of rationality of human adversaries, and evaluation of the optimal security strategy found.