Mixed-Integer Programming versus Constraint Programming for the Travelling Salesman Problem with Time Windows and Clustered Backhauls: A School-Meal Delivery Case Study - Santiyuda, Kadek Gemilang (IJCCS (Indonesian Journal of Computing and Cybernetics Systems), 2026)
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.