The traveling salesman problem with pickup, delivery, and ride-time constraints
| Autor: | Lawrence Bodin, Enrico Bartolini, Aristide Mingozzi |
|---|---|
| Přispěvatelé: | Enrico Bartolini, Lawrence Bodin, Aristide Mingozzi |
| Rok vydání: | 2015 |
| Předmět: |
Mathematical optimization
Operations research Computer Networks and Communications Computer science 0211 other engineering and technologies 02 engineering and technology Travelling salesman problem dual ascent 0502 economics and business Pickup Computational analysis branch-and-price cut-and-column generation dual ascent ta512 ta113 Service (business) ta112 050210 logistics & transportation 021103 operations research Branch and price ta111 05 social sciences cut-and-column generation Volume (computing) Travel cost Constraint (information theory) branch-and-price Hardware and Architecture Software Information Systems |
| Zdroj: | Networks. 67:95-110 |
| ISSN: | 0028-3045 |
| DOI: | 10.1002/net.21663 |
| Popis: | In the traveling salesman problem with pickup, delivery, and ride-time constraints (TSPPD-RT), a vehicle located at a depot is required to service a number of requests where the requests are known before the route is formed. Each request consists of (i) a pickup location (origin), (ii) a delivery location (destination), and (iii) a maximum allowable travel time from the origin to the destination (maximum ride-time). The problem is to design a tour for the vehicle that (i) starts and ends at the depot, (ii) services all requests, (iii) ensures that each request's ride-time does not exceed its maximum ride-time, and (iv) minimizes the total travel time required by the vehicle to service all requests (objective function). A capacity constraint that may be present is that the weight or volume of the undelivered requests on the vehicle must always be no greater than the vehicle's capacity. In this article, we concurrently analyze the TSPPD-RT with capacity constraints and without capacity constraints. We describe two mathematical formulations of the problem. These formulations are used to derive new lower bounds on the solution to the problem. Then, we provide two exact methods for finding the optimal route that minimizes the total travel cost. Our extensive computational analysis on both versions of the TSPPD-RT shows that the proposed algorithms are capable of solving to optimality instances involving up to 50 requests. © 2015 Wiley Periodicals, Inc. NETWORKS, 2015 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text