A Two-Index Formulation for the Fixed-Destination Multi-Depot Asymmetric Travelling Salesman Problem and Some Extensions

We introduce a compact formulation for the fixed-destination multi-depot asymmetric travelling salesman problem (FD-mATSP). It consists of m salesmen distributed among D depots who depart from and return to their respective origins after visiting a set of customers. The proposed model exploits the multi-depot aspect of the problem by labelling the arcs to identify the nodes that belong to the same tour. Our experimental investigation shows that the proposed-two index formulation is versatile and effective in modelling new variations of the FD-mATSP compared with existing formulations. We demonstrate this by applying it for the solution of two important extensions of the FD-mATSP that arise in logistics and manufacturing environments.

• Publication year

  2022

• Venue

  Informatica

• Publication date

  2022-06-01

• Fields of study

  Mathematics, Business, Computer Science

• Identifiers
  DOI 10.15388/22-INFOR485
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Compact formulations for multi-depot routing problems: Theoretical and computational comparisons

  2020cited by this paper
• Multi-depot vehicle routing problem: a comparative study of alternative formulations

  2020cited by this paper
• A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem

  2018cited by this paper
• The milk collection problem with blending and collection points

  2017cited by this paper
• Modeling, Analysis, and Exact Algorithms for Some Biomass Logistics Supply Chain Design and Routing Problems

  2016cited by this paper
• Intermediate Facilities in Freight Transportation Planning: A Survey

  2016cited by this paper
• Study on Multi-Depot Collaborative Transportation Problem of Milk-Run Pattern

  2016cited by this paper
• A literature review on the vehicle routing problem with multiple depots

  2015cited by this paper
• Urban bicycles renting systems: Modelling and optimization using nature-inspired search methods

  2014cited by this paper
• Vehicle Routing Problem

  2013influential reference
• Exact and Compact Formulation of the Fixed-Destination Travelling Salesman Problem by Cycle Imposement Through Node Currents

  2013influential reference
• Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

  2012cited by this paper
• A Survey on the Vehicle Routing Problem and Its Variants

  2012cited by this paper
• An Effective Genetic Algorithm for the Vehicle Routing Problem with Multiple Depots

  2011cited by this paper
• Traveling Salesman Problem, Theory and Applications

  2010cited by this paper
• A reactive tabu search algorithm for the multi-depot container truck transportation problem

  2009cited by this paper
• An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem

  2007cited by this paper
• The vehicle routing problem: Latest advances and new challenges

  2007cited by this paper
• Integer linear programming formulations of multiple salesman problems and its variations

  2006cited by this paper
• The traveling salesman: computational solutions for TSP applications

  1994cited by this paper
• The swapping problem

  1992cited by this paper
• The traveling salesman problem: An overview of exact and approximate algorithms

  1992cited by this paper
• The vehicle routing problem: An overview of exact and approximate algorithms

  1992cited by this paper
• THE TRAVELING SALESMAN PROBLEM A Guided Tour of Combinatorial Optimization

  1986cited by this paper
• The Travelling Salesman Problem and Related Problems

  1978cited by this paper

• Cooperative driving route planning based on asymmetric multi-agent path planning problem with limited service area constraints

  2025cites this paper
• Hybrid optimization of logistics distribution paths using neural networks and fuzzy logic

  2025influential citation
• Compact Integer Programs for Depot-Free Multiple Traveling Salesperson Problems

  2023cites this paper