Proceedings

Fleet Design Optimisation from Historical Data Using Constraint Programming and Large Neighbourhood Search

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 4185-4188.

© 2016 International Joint Conferences on Artificial Intelligence

Abstract

We present an original approach to compute efficient mid-term fleet configurations at the request of a Queensland-based long-haul trucking carrier. Our approach considers one year's worth of demand data, and employs a constraint programming (CP) model and an adaptive large neighbourhood search (LNS) scheme to solve the underlying multi-day multi-commodity split delivery capacitated vehicle routing problem. This paper is an adaptation of the Best Application Paper at CP'15, published in the Constraints journal with the same title.

  1. [Archetti and Speranza, 2008] Claudia Archetti and Maria- Grazia Speranza. The split delivery vehicle routing prob- lem: A survey. In Bruce Golden, S. Raghavan, and Ed- ward Wasil, editors, The Vehicle Routing Problem: Lat- est Advances and New Challenges, volume 43 of Opera- tions Research/Computer Science Interfaces, pages 103- 122. Springer US, 2008.
  2. [Belfiore and Yoshizaki, 2013] Patrícia Belfiore and Hugo T.Y. Yoshizaki. Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries. Computers & Industrial Engineering, 64(2):589-601, 2013.
  3. [Bräysy et al., 2008] Olli Bräysy, Wout Dullaert, Geir Hasle, David Mester, and Michel Gendreau. An effective mul- tirestart deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. Transportation Science, 42(3):371-386, 2008.
  4. [Crainic, 2003] Teodor Gabriel Crainic. Long-haul freight transportation. In Randolph W. Hall, editor, Handbook of Transportation Science, volume 56 of International Series in Operations Research & Management Science, pages 451-516. Springer US, 2003.
  5. [Dantzig and Ramser, 1959] George B Dantzig and John H Ramser. The truck dispatching problem. Management sci- ence, 6(1):80-91, 1959.
  6. [Dell'Amico et al., 2007] Mauro Dell'Amico, Michele Monaci, Corrado Pagani, and Daniele Vigo. Heuristic approaches for the fleet size and mix vehicle routing problem with time windows. Transportation Science, 41(4):516-526, 2007.
  7. [Di Gaspero and Urli, 2014] Luca Di Gaspero and Tommaso Urli. A cp/lns approach for multi-day homecare schedul- ing problems. In Hybrid Metaheuristics, pages 1-15. Springer, 2014.
  8. [Di Gaspero et al., 2015] Luca Di Gaspero, Andrea Rendl, and Tommaso Urli. Balancing bike sharing systems with constraint programming. Constraints, pages 1-31, 2015.
  9. [Dror and Trudeau, 1989] Moshe Dror and Pierre Trudeau. Savings by split delivery routing. Transportation Science, 23(2):141-145, 1989.
  10. [Dror and Trudeau, 1990] Moshe Dror and Pierre Trudeau. Split delivery routing. Naval Research Logistics (NRL), 37(3):383-402, 1990.
  11. [Kilby and Shaw, 2006] Philip Kilby and Paul Shaw. Vehi- cle routing. Handbook of constraint programming, pages 799-834, 2006.
  12. [Kilby and Urli, 2015] Philip Kilby and Tommaso Urli. Fleet design optimisation from historical data using constraint programming and large neighbourhood search. Con- straints, pages 1-20, 2015.
  13. [Kytöjoki et al., 2007] Jari Kytöjoki, Teemu Nuortio, Olli Bräysy, and Michel Gendreau. An efficient variable neighborhood search heuristic for very large scale vehi- cle routing problems. Computers & Operations Research, 34(9):2743-2757, 2007.
  14. [Pisinger and Ropke, 2010] David Pisinger and Stefan Ropke. Large neighborhood search. In Handbook of Metaheuristics, pages 399-419. Springer, 2010.
  15. [Ropke and Pisinger, 2006] Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4):455-472, 2006.
  16. [Schulte et al., 2015] Christian Schulte, Guido Tack, and Mikael Z. Lagerkvist. Modeling and Programming with Gecode. Schulte, Christian and Tack, Guido and Lagerkvist, Mikael Z., 2015.
  17. [Shaw, 1998] Paul Shaw. Using constraint programming and local search methods to solve vehicle routing problems.
  18. In Michael J. Maher and Jean-Francois Puget, editors, CP'98: the 4th International Conference on Principles and Practice of Constraint Programming, 1998, Proceed- ings of, volume 1520 of Lecture Notes in Computer Sci- ence, pages 417-431. Springer, 1998.
  19. [Toth and Vigo, 2002] Paolo Toth and Daniele Vigo. The Ve- hicle Routing Problem. Society for Industrial and Applied Mathematics, 2002.
  20. [Vidal et al., 2014] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, and Christian Prins. A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3):658- 673, 2014.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards