Melola Discovery

← Melola Discovery

Open access Jurnal SINTA 2

Mixed-Integer Programming versus Constraint Programming for the Travelling Salesman Problem with Time Windows and Clustered Backhauls: A School-Meal Delivery Case Study

IJCCS (Indonesian Journal of Computing and Cybernetics Systems) · Vol. 20 No. 3 (2026) · pp. 343–352

DOI
10.22146/ijccs.122506
ISSN
2460-7258, 1978-1520
Published
2026-07-31
Publisher
IndoCEISS in colaboration with Universitas Gadjah Mada, Indonesia.
Language
eng
License
creativecommons.org/licenses/by-sa/4.0

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

Collaboration network of the authors

No co-authors found in Melola yet.

Metadata source: OAI-PMH (metadata jurnal) https://journal.ugm.ac.id/ijccs/oai, first harvested 26 Okt 2026, last seen 26 Okt 2026.
Original metadata (oai_dc) 
<oai_dc:dc xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/  http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
	<dc:title xml:lang="en-US">Mixed-Integer Programming versus Constraint Programming for the Travelling Salesman Problem with Time Windows and Clustered Backhauls: A School-Meal Delivery Case Study</dc:title>
	<dc:creator>Santiyuda, Kadek Gemilang</dc:creator>
	<dc:subject xml:lang="en-US">Operations Research; Computer Science</dc:subject>
	<dc:subject xml:lang="en-US">Travelling Salesman Problem with Time Windows, Clustered Backhauls, Constraint Programming, Mixed-integer Programming, Food Distribution</dc:subject>
	<dc:description xml:lang="en-US">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.</dc:description>
	<dc:publisher xml:lang="en-US">IndoCEISS in colaboration with Universitas Gadjah Mada, Indonesia.</dc:publisher>
	<dc:contributor xml:lang="en-US"></dc:contributor>
	<dc:date>2026-07-31</dc:date>
	<dc:type>info:eu-repo/semantics/article</dc:type>
	<dc:type>info:eu-repo/semantics/publishedVersion</dc:type>
	<dc:type xml:lang="en-US"></dc:type>
	<dc:format>application/pdf</dc:format>
	<dc:identifier>https://journal.ugm.ac.id/ijccs/article/view/122506</dc:identifier>
	<dc:identifier>10.22146/ijccs.122506</dc:identifier>
	<dc:source xml:lang="en-US">IJCCS (Indonesian Journal of Computing and Cybernetics Systems); Vol 20, No 3 (2026): July; 343-352</dc:source>
	<dc:source>2460-7258</dc:source>
	<dc:source>1978-1520</dc:source>
	<dc:language>eng</dc:language>
	<dc:relation>https://journal.ugm.ac.id/ijccs/article/view/122506/45572</dc:relation>
	<dc:rights xml:lang="en-US">Copyright (c) 2026 IJCCS (Indonesian Journal of Computing and Cybernetics Systems)</dc:rights>
	<dc:rights xml:lang="en-US">http://creativecommons.org/licenses/by-sa/4.0</dc:rights>
</oai_dc:dc>