* Corresponding Author
Mixed-Integer Programming versus Constraint Programming for the Travelling Salesman Problem with Time Windows and Clustered Backhauls: A School-Meal Delivery Case Study
https://doi.org/10.22146/ijccs.122506 Kadek Gemilang Santiyuda(1*)
(1) National Taiwan University of Science and Technology
(*) Corresponding Author
Abstract
Under Indonesia’s Makanan Bergizi Gratis (MBG), a vehicle delivers freshly cooked meals to schools within their lunchtime windows, takes a driver break, and then collects the reusable containers before returning to the kitchen. We study this route as a Travelling Salesman Problem with Time Windows and Clustered Backhauls (TSPTW-CB). Each school’s container collection is paired with its delivery, deliveries come before any collection, and a food-freshness limit fixes a single dispatch time for the trip. We formulate the problem in two ways. First, a mixed-integer linear program (MILP) solved with Gurobi. The second is a constraint program (CP) solved with OR-Tools CP-SAT. We compare them on route instances built from a real case study in Bali, Indonesia, and we check every result with an independent schedule simulator. On feasible instances the two solvers are equally fast and return the same optimal route. The difference appears on infeasible instances. The CP model proves in a fraction of a second that one vehicle cannot serve a set of schools, while the MILP does not finish within ten minutes. This feasibility question decides how many vehicles a kitchen needs, so constraint programming is the better tool for this route.
Keywords
References
P. Toth and D. Vigo, Eds., Vehicle Routing: Problems, Methods, and Applications, 2nd ed. Philadelphia, PA, USA: SIAM, 2014.
M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Oper. Res., vol. 35, no. 2, pp. 254–265, 1987.
N. Ascheuer, M. Fischetti, and M. Grötschel, “Solving the asymmetric travelling salesman problem with time windows by branch-and-cut,” Math. Program., vol. 90, no. 3, pp. 475–506, 2001.
M. Goetschalckx and C. Jacobs-Blecha, “The vehicle routing problem with backhauls,” Eur. J. Oper. Res., vol. 42, no. 1, pp. 39–51, 1989.
G. Nagy and S. Salhi, “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,” Eur. J. Oper. Res., vol. 162, no. 1, pp. 126–141, 2005.
S. N. Parragh, K. F. Doerner, and R. F. Hartl, “A survey on pickup and delivery problems, Part I: Transportation between customers and depot,” J. Betriebswirtschaft, vol. 58, no. 1, pp. 21–51, 2008.
A. Goel, “Vehicle scheduling and routing with drivers’ working hours,” Transp. Sci., vol. 43, no. 1, pp. 17–26, 2009.
M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems,” J. Soc. Ind. Appl. Math., vol. 10, no. 1, pp. 196–210, 1962.
Y. Dumas, J. Desrosiers, E. Gélinas, and M. M. Solomon, “An optimal algorithm for the traveling salesman problem with time windows,” Oper. Res., vol. 43, no. 2, pp. 367–371, 1995.
P. Baptiste, C. Le Pape, and W. Nuijten, Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Boston, MA, USA: Kluwer, 2001.
P. Laborie, J. Rogerie, P. Shaw, and P. Vilím, “IBM ILOG CP Optimizer for scheduling,” Constraints, vol. 23, no. 2, pp. 210–250, 2018.
P. Kilby and P. Shaw, “Vehicle routing,” in Handbook of Constraint Programming, F. Rossi, P. van Beek, and T. Walsh, Eds. Amsterdam, The Netherlands: Elsevier, 2006, pp. 801–836.
L. Perron and V. Furnon, “OR-Tools,” Google. [Online]. Available: https://developers.google.com/optimization
Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2024. [Online]. Available: https://www.gurobi.com
R. Cuda, G. Guastaroba, and M. G. Speranza, “A survey on two-echelon routing problems,” Comput. Oper. Res., vol. 55, pp. 185–199, 2015.
G. Desaulniers, O. B. G. Madsen, and S. Ropke, “The vehicle routing problem with time windows,” in Vehicle Routing: Problems, Methods, and Applications, 2nd ed., P. Toth and D. Vigo, Eds. Philadelphia, PA, USA: SIAM, 2014, pp. 119–159.
DOI: https://doi.org/10.22146/ijccs.122506
Article Metrics
Abstract views : 0
Copyright (c) 2026 IJCCS (Indonesian Journal of Computing and Cybernetics Systems)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
View My Stats1