The multicommodity traveling salesman problem with priority prizes: a mathematical model and metaheuristics
- PDF / 763,441 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 129 Views
(2019) 38:188
The multicommodity traveling salesman problem with priority prizes: a mathematical model and metaheuristics Tiago Tiburcio da Silva1 · Antônio Augusto Chaves1 · Horacio Hideki Yanasse1 · Henrique Pacca Loureiro Luna2 Received: 4 February 2019 / Revised: 24 May 2019 / Accepted: 29 September 2019 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2019
Abstract The classic Traveling Salesman Problem (TSP) only considers the costs involved in the routes and does not differentiate products or customers. Logistic companies face conflict between operational costs, customers with different categories of products, and customer satisfaction, which is directly related to delivery time. This paper presents a new mathematical model for a TSP with variable costs and priority prizes, taking into account the customer’s product and preference values. This problem is denoted as the Multicommodity Traveling Salesman Problem with Priority Prizes (MTSPPP). Two versions of the Biased RandomKey Genetic Algorithm (BRKGA) are proposed to solve medium and large instances of the MTSPPP. Computational tests were performed, using modified instances based on classical TSP instances. The proposed methods have proved to be efficient in solving the MTSPPP. Keywords Traveling salesman · Multicommodity · Priority · Genetic algorithm Mathematics Subject Classification 90-08
1 Introduction The Traveling Salesman Problem (TSP) is a well-known NP-hard problem in network optimization (Applegate et al. 2006; Dantzig et al. 1954; Flood 1956; Lawler et al. 1985). It consists of determining a minimum cost Hamiltonian path, visiting all customers only once,
Communicated by Hector Cancela.
B
Tiago Tiburcio da Silva [email protected] Antônio Augusto Chaves [email protected] Horacio Hideki Yanasse [email protected] Henrique Pacca Loureiro Luna [email protected]
1
Univ. Fed. of São Paulo, São José dos Campos, SP 12231-280, Brazil
2
Federal University of Alagoas, Maceió, AL 57072-970, Brazil
123
188
Page 2 of 25
T. T. Silva et al.
and returning to the starting point. The TSP arises in many applied settings, such as drilling of printed circuit boards (Grotschel et al. 1991), the order-picking problem in depots (Ratliff and Rosenthal 1983), the school bus routing problem (Angel et al. 1972), the defender–attacker– defender problem (Lozano et al. 2017), and the maritime logistics (Malaguti et al. 2018). The TSP and most of its variations are oriented by costs and, in the literature, we hardly see studies considering different demands. One variation that does consider different demands is the Multicommodity Traveling Salesman Problem (MTSP) (Sarubbi 2003; Sarubbi and Luna 2007; Sarubbi et al. 2007). In the MTSP, product types and quantities that pass through a route connecting two customers are considered in the total cost. In practice, customers with larger demands or more precious or high-risk products must be delivered with a higher priority. For example, sensitive materials may require special transp
Data Loading...
