Solving the Single Traveling Repairman Problem with Constraint Programming

Çevik N., Yıldız Ş. A.

International İzmir Democracy Engineering (IDU) Symposium, IES'22, 28 - 30 October 2022, pp.3

  • Publication Type: Conference Paper / Summary Text
  • Page Numbers: pp.3
  • Dokuz Eylül University Affiliated: Yes


The Traveling Repairman Problem (TRP)  is often solved in the literature using different solution strategies in many domains with deterministic data. The TRP  has been modeled differently according to different objective functions, problem constraints and properties. Different objectives such as profit maximization, waiting time minimization, and cost minimization can be observed. For the traditional TRP, there are certain characteristics of the problem, such as; each customer needing to be served by one repairman, and the travel starts from the depot and ends at a terminal node while creating a route of customers. The TRP with profit maximization is formulated around a repairman or a server who needs to follow a route to satisfy the service demands of the customers. Since the objective is profit maximization, there is no condition to satisfy all customer demands as long as it is not profitable.  In this study, a constraint programming model has been proposed for the TRP with profits. As the problem size increases, reaching the optimal solution becomes impossible and long solution times are encountered even for feasible solutions. The model was tested with the benchmark instances. The performance comparison of the existing integer programming models and the proposed constraint programming model has been carried out over the solution time and percent optimality gap. Compared to the best-performing integer programming model in the literature, the developed constraint programming model successfully reached high-quality solutions in reasonable computation times.