Publications

  1. 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}
    }
    
    Abstract
    The 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.
  2. Mahéo, A., Urli, T., & Kilby, P. (2016). Fleet Size and Mix Split-Delivery Vehicle Routing. 1–22. http://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 = {http://arxiv.org/abs/1612.01691},
      year = {2016},
      note = {arXiv:1612.01691 [cs.AI]}
    }
    
    Abstract
    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.
  3. Morita, H., & Mahéo, A. (2014). Classification Model Using Contrast Patterns and GRASP. Journal of Information Assurance and Security, 9(5), 235–243. http://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 = {http://www.mirlabs.net/jias/secured/Volume9-Issue5/vol9-issue5.html},
      volume = {9},
      year = {2014}
    }
    
    Abstract
    The 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.
  4. 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 = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7113126},
      year = {2013}
    }
    
    Abstract
    The 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.

Abstract

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.

Abstract

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.