Models and linearizations for the Traveling Car Renter with Passengers
| Autor: | Elizabeth Ferreira Gouvea Goldbarg, Matheus da Silva Menezes, Zailton Sachas Amorim Calheiros, Gustavo de Araujo Sabry, Marco César Goldbarg |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
021103 operations research Control and Optimization Computer science business.industry 0211 other engineering and technologies Linear model Computational intelligence 010103 numerical & computational mathematics 02 engineering and technology Extension (predicate logic) 01 natural sciences Travelling salesman problem Renting Linearization 0101 mathematics business Integer programming |
| Zdroj: | Optimization Letters. 15:59-81 |
| ISSN: | 1862-4480 1862-4472 |
| Popis: | In this study, we introduce the Traveling Car Renter with Passengers (CaRSP), an extension of the Traveling Car Renter Problem (CaRS). The latter generalizes the Traveling Salesman Problem (TSP) by allowing several cars with different costs to be available for use during the salesman’s tour. In the CaRSP, passengers are allowed in the salesman’s car and share trip expenses with the driver. Passengers have different pick-up and drop-off points and share the costs of the part of the trip in which they are in the vehicle. We present two mixed integer programming formulations for the CaRSP. The first model is based on the Dantzig-Fulkerson-Johnson formulation for the TSP and the second on the Miller–Tucker–Zemlin formulation. The formulations are linearized regarding two different techniques, resulting in four linear models. One of those linearization techniques is proposed in this study. We present the results of an experiment in which 54 instances are submitted to two optimization solvers, concerning the four linear models introduced. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink