1761. Continuous approximation model for estimating average tour length in prize collecting traveling salesman problem and application
Invited abstract in session MB-59: Routing decisions , stream Transportation.
Monday, 10:30-12:00Room: Liberty 1.14
Authors (first author is the speaker)
| 1. | Daisuke Hasegawa
|
| Center for Real Estate Innovation, The University of Tokyo | |
| 2. | Yuichiro Miyamoto
|
| Sophia University | |
| 3. | Toshio Nemoto
|
| Bunkyo University |
Abstract
The prize collecting traveling salesman problem (PCTSP) is to find routes and subset of nodes that minimize a tour distance with the constraint to be less than given rewards by visiting nodes. This study estimates the PCTSP travel distance using a continuous approximation model. Continuous approximation model does not search for routes, but it estimates the travel distance using the area of the region and the number of nodes. In our proposed model, the size of the delivery zone and the number of nodes is given, and the spatial distribution of the penalty is represented as a demand function. It replicates the concentration of population and economic value in the center of cities.
This model enables the analytical derivation of the average tour length required to achieve a certain level of reward. By applying the proposed model, we propose a method for estimating the tour length of the PCTSP in cases involving multiple delivery zones.
Keywords
- Transportation
- Vehicle Routing
- Logistics
Status: accepted
Back to the list of papers