Publications
- Mahéo, A., Rossit, D. G., & Kilby, P. (2021). A Benders Decomposition Approach for an Integrated Bin Allocation and Vehicle Routing Problem in Municipal Waste Management. In D. A. Rossit, F. Tohmé, & G. Mejía Delgadillo (Eds.), Production Research (pp. 3–18). Springer International Publishing. https://doi.org/10.1007/978-3-030-76310-7_1 [PDF] BibTex
@inproceedings{maheo2020icpr, url_file = {https://arthur.maheo.net/pdfs/maheo2020icpr.pdf}, author = {Mah{\'e}o, Arthur and Rossit, Diego Gabriel and Kilby, Philip}, editor = {Rossit, Daniel Alejandro and Tohm{\'e}, Fernando and Mej{\'i}a Delgadillo, Gonzalo}, title = {A Benders Decomposition Approach for an Integrated Bin Allocation and Vehicle Routing Problem in Municipal Waste Management}, booktitle = {Production Research}, year = {2021}, publisher = {Springer International Publishing}, address = {Cham}, pages = {3--18}, isbn = {978-3-030-76310-7}, url = {https://doi.org/10.1007/978-3-030-76310-7_1} }AbstractThe municipal solid waste system is a complex reverse logistic chain which comprises several optimisation problems. Although these problems are interdependent – i.e., the solution to one of the problems restricts the solution to the other – they are usually solved sequentially in the related literature because each is usually a computationally complex problem. We address two of the tactical planning problems in this chain by means of a Benders decomposition approach: determining the location and/or capacity of garbage accumulation points, and the design of collection routes for vehicles. We also propose a set of valid inequalities to speed up the resolution process. Our approach manages to solve medium-sized real-world instances in the city of Bahía Blanca, Argentina, showing smaller computing times in comparison to solving a full MIP model.
- Mahéo, A., Zhao, S., Hassan, A., Harabor, D., Stuckey, P., & Wallace, M. (2021). Customised Shortest Paths Using a Distributed Reverse Oracle. In H. Ma & I. Serina (Eds.), Proceedings of the 14th Annual Symposium on Combinatorial Search (SoCS 2021) (pp. 79–87). AAAI Press. [PDF] BibTex
@inproceedings{maheo2021socs, url_file = {https://arthur.maheo.net/pdfs/maheo2021socs.pdf}, title = {Customised Shortest Paths Using a Distributed Reverse Oracle}, author = {Mah\'{e}o, Arthur and Zhao, Shizhe and Hassan, Afzaal and Harabor, Daniel and Stuckey, Peter and Wallace, Mark}, booktitle = {{Proceedings of the 14th Annual Symposium on Combinatorial Search (SoCS 2021)}}, year = {2021}, month = jul, pages = {79--87}, editor = {Ma, Hang and Serina, Ivan}, publisher = {AAAI Press}, address = {2275 East Bayshore Road, Suite 160 Palo Alto, California 94303}, isbn = {978-1-57735-870-1} }AbstractWe consider the design and implementation of a centralised oracle that provides commuters with customised and congestion-aware driving directions. Computing directions for a single journey is straightforward, but doing so at city-scale, in real-time, and under changing conditions is extremely challenging. In this work we describe a new type of centralised oracle which combines a fast, real-time database-driven path planner with a distributed query management system. We solve all queries online and we allow large-scale changes to the underlying graph metric, from one query to the next, all without any database repair. To maximise throughput we also consider a variety of query types, including optimal, bounded suboptimal, time-budgeted and k-prefix. Experiments on a small number of commodity machines show that our approach solves hundreds of thousands of queries per second, and more; sufficient to provide real-time routing for all commuter trips in city of Melbourne, Australia, during peak hour.
- Mahéo, A., Belieres, S., Adulyasak, Y., & Cordeau, J.-F. (2020). Unified Branch-and-Benders-Cut for Two-Stage Stochastic Mixed-Integer Programs. Les Cahiers Du GERAD, G-2020-54. [PDF] BibTex
@article{maheo2020brandec, url_file = {https://arthur.maheo.net/pdfs/maheo2020brandec.pdf}, title = {Unified Branch-and-{Benders}-Cut for Two-Stage Stochastic Mixed-Integer Programs}, author = {Mah{\'e}o, Arthur and Belieres, Simon and Adulyasak, Yossiri and Cordeau, Jean-Fran{\c{c}}ois}, journal = {Les Cahiers du GERAD}, volume = {G-2020-54}, year = {2020}, month = oct }AbstractTwo-stage stochastic programs are a class of stochastic problems where data uncertainty is often discretized into scenarios, making them amenable to solution approaches such as Benders decomposition. However, classic Benders decomposition is not applicable to general two-stage stochastic mixed-integer programs due to the restriction that the second stage variables must be continuous. We propose a novel Benders decomposition-based framework that accommodates mixed-integer variables in both stages as well as uncertainty in all the recourse parameters. The proposed approach is a unified branch-and-Benders algorithm, where we use a heuristic to maintain a global upper bound and a post-processing phase to determine an optimal solution. We also study how enhanced Benders decomposition strategies such as the partial decomposition technique can be used to improve the algorithm’s convergence. Through an extensive series of experiments, we demonstrate that the proposed framework performs better than state-of-the-art methods. It is able to solve some problem instances with more than one million variables in reasonable time.
- Mahéo, A., Kilby, P., & Van Hentenryck, P. (2017). Benders Decomposition for the Design of a Hub and Shuttle Public Transit System. Transportation Science. https://doi.org/10.1287/trsc.2017.0756 [PDF] BibTex
@article{maheo2017benders, author = {Mah{\'{e}}o, Arthur and Kilby, Philip and {Van Hentenryck}, Pascal}, url_file = {https://arthur.maheo.net/pdfs/maheo2015benders.pdf}, keywords = {benders decomposition,combinatorial optimisation,cut bundling,multimodal transportation,optimal cuts,pareto}, title = {{Benders Decomposition for the Design of a Hub and Shuttle Public Transit System}}, doi = {10.1287/trsc.2017.0756}, year = {2017}, journal = {Transportation Science}, publisher = {INFORMS} }AbstractThe BusPlus project aims at improving the off-peak hours public transit service in Canberra, Australia. To address the difficulty of covering a large geographic area, BusPlus proposes a hub and shuttle model consisting of a combination of a few high-frequency bus routes between key hubs and a large number of shuttles that bring passengers from their origin to the closest hub and take them from their last bus stop to their destination. This paper focuses on the design of bus network and proposes an efficient solving method to this multimodal network design problem based on the Benders decomposition method. Starting from a MIP formulation of the problem, the paper presents a Benders decomposition approach using dedicated solution techniques for solving independent sub-problems, Pareto optimal cuts, cut bundling, and core point update. Computational results on real-world data from Canberra’s public transit system justify the design choices and show that the approach outperforms the MIP formulation by two orders of magnitude. Moreover, the results show that the hub and shuttle model may decrease transit time by a factor of 2, while staying within the costs of the existing transit system.
- Mahéo, A., Urli, T., & Kilby, P. (2016). Fleet Size and Mix Split-Delivery Vehicle Routing. 1–22. https://arxiv.org/abs/1612.01691 [PDF] BibTex
@article{Maheo2016, archiveprefix = {arXiv}, arxivid = {1612.01691}, author = {Mah{\'{e}}o, Arthur and Urli, Tommaso and Kilby, Philip}, eprint = {1612.01691}, url_file = {https://arthur.maheo.net/pdfs/maheo2016fleet.pdf}, keywords = {constraint programming,fleet size and mix,integer programming,rich vehicle routing,split delivery}, month = dec, pages = {1--22}, title = {{Fleet Size and Mix Split-Delivery Vehicle Routing}}, url = {https://arxiv.org/abs/1612.01691}, year = {2016}, note = {arXiv:1612.01691 [cs.AI]} }AbstractIn the classic Vehicle Routing Problem (VRP) a fleet of of vehicles has to visit a set of customers while minimising the operations’ costs. We study a rich variant of the VRP featuring split deliveries, an heterogeneous fleet, and vehicle-commodity incompatibility constraints. Our goal is twofold: define the cheapest routing and the most adequate fleet. To do so, we split the problem into two interdependent components: a fleet design component and a routing component. First, we define two Mixed Integer Programming (MIP) formulations for each component. Then we discuss several improvements in the form of valid cuts and symmetry breaking constraints. The main contribution of this paper is a comparison of the four resulting models for this Rich VRP. We highlight their strengths and weaknesses with extensive experiments. Finally, we explore a lightweight integration with Constraint Programming (CP). We use a fast CP model which gives good solutions and use the solution to warm-start our models.
- Morita, H., & Mahéo, A. (2014). Classification Model Using Contrast Patterns and GRASP. Journal of Information Assurance and Security, 9(5), 235–243. https://www.mirlabs.net/jias/secured/Volume9-Issue5/vol9-issue5.html BibTex
@article{morita2016classification, author = {Morita, Hiroyuki and Mah{\'{e}}o, Arthur}, journal = {Journal of Information Assurance and Security}, keywords = {GRASP,cacp,classification predictive,contrast pattern}, number = {5}, pages = {235--243}, title = {{Classification Model Using Contrast Patterns and GRASP}}, url = {https://www.mirlabs.net/jias/secured/Volume9-Issue5/vol9-issue5.html}, volume = {9}, year = {2014} }AbstractThe volume of historical purchasing data has become huge, and it includes many kinds of data attributes. Specifically, categorical data, such as product codes, are difficult to handle. If the product is purchased repeatedly, we can aggregate the data and use the product data as a numerical attribute. However, if the item was purchased only once, we can get only very basic information, such as whether it was purchased or not. To use the information more effectively, we can use a subset of these purchased items as a purchasing pattern within the set of items. Some classification predictive models that use these patterns were proposed, including the classification by aggregating contrast patterns (CACP). However, the model sometimes produces too many specific patterns. This is not a problem for predictions, but interpreting the model can become too complicated to implement efficiently. In this paper, we propose a method to decrease the number of patterns in the classification model for CACP. The proposed method uses the meta-heuristics algorithm known as greedy randomized adaptive search procedure (GRASP). A computational experiment shows that we can remove extra patterns and construct the model, while maintaining its performance level.
- Morita, H., & Mahéo, A. (2013). Efficient predictive classification model using CACP and GRASP. 2013 Third World Congress on Information and Communication Technologies (WICT 2013), 147–153. https://doi.org/10.1109/WICT.2013.7113126 BibTex
@conference{morita2013efficient, author = {Morita, Hiroyuki and Mah{\'{e}}o, Arthur}, booktitle = {2013 Third World Congress on Information and Communication Technologies (WICT 2013)}, doi = {10.1109/WICT.2013.7113126}, isbn = {978-1-4799-3230-6}, keywords = {CACP,GRASP,classification predictive model,contrast pattern}, month = dec, pages = {147--153}, publisher = {IEEE}, title = {{Efficient predictive classification model using CACP and GRASP}}, url = {https://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7113126}, year = {2013} }AbstractThe volume of historical purchasing data has become huge, and it includes many kinds of data attributes. Specifically, categorical data, such as product codes, are difficult to handle. If the product is purchased repeatedly, we can aggregate the data and use the product data as a numerical attribute. However, if the item was purchased only once, we can get only very basic information, such as whether it was purchased or not. To use the information more effectively, we can use a subset of these purchased items as a purchasing pattern within the set of items. Some classification predictive models that use these patterns were proposed, including the classification by aggregating contrast patterns (CACP). However, the model sometimes produces too many specific patterns. This is not a problem for predictions, but interpreting the model can become too complicated to implement efficiently. In this paper, we propose a method to decrease the number of patterns in the classification model for CACP. The proposed method uses the meta-heuristics algorithm known as greedy randomized adaptive search procedure (GRASP). A computational experiment shows that we can remove extra patterns and construct the model, while maintaining its performance level.
Presentations
Below is a list of presentations I gave at different conferences, or invited talks during internships. Click on the title to be redirected to the slides proper, and on the “Abstract” button to see the abstract.
CIRRELT 2016
During my internship in Autumn 2016 at CIRRELT in Montréal, Canada, with professor Jean-François Cordeau, I was invited to give a talk on the BusPlus project, a public transportation network design problem for Canberra, Australia.
Canberra is a planned city designed by American architect Walter Griffin in 1913. It features a large number of semi-autonomous towns separated by greenbelts. As a result, Canberra covers a wide geographic area, which makes public transportation particularly challenging.
We propose to tackle the problem of off-peak transportation by using a Bus and Shuttle network where buses will run between major hubs throughout the city at regular intervals, while a fleet of on-demand shuttles will take care of the “last mile” problem.
We first propose a model based on the Hub-Arc Location Problem (HALP). The HALP can be seen as a two-level decision problem deciding which arcs to open first and then how to route the flow at minimum cost. As such, its structure appears ideally suited for Benders decomposition.
Benders decomposition is a well-known partitioning method to solve large mixed integer programs. We develop a Benders decomposition approach with the following improvements: cut disaggregation, Pareto optimal sub-problem, and core point update.
VeRoLog 2016
During VeRoLog 2016, in Nantes, France, I presented our work on modelling a Rich VRP variant where constraints stemmed from a tender initiated by a grocery delivery company based in Queensland, Australia.
In the classic Vehicle Routing Problem (VRP) a fleet of of vehicles has to visit a set of customers while minimising the operations’ costs. We study a rich variant of the VRP featuring split deliveries, an heterogeneous fleet, and vehicle-commodity incompatibility constraints. Our goal is twofold: define the cheapest routing and the most adequate fleet.
To do so, we split the problem into two interdependent components: a fleet design component and a routing component. First, we define two Mixed Integer Programming (MIP) formulations for each component. Then we discuss several improvements in the form of valid cuts and symmetry breaking constraints.
The main contribution of this paper is a comparison of the four resulting models for this Rich VRP. We highlight their strengths and weaknesses with extensive experiments.
Finally, we explore a lightweight integration with Constraint Programming (CP). We use a fast CP model which gives good solutions and use the solution to warm-start our models.