The traveling purchaser problem with time-dependent quantities. (English) Zbl 1391.90502
Summary: The deterministic traveling purchaser problem looks for a tour visiting a subset of markets in order to satisfy a positive discrete demand for some products at minimum traveling and purchasing costs. In this paper, we assume that the quantities available in the markets for all the products are time-varying decreasing at a constant rate. We propose a compact mixed integer formulation for the problem, and strengthen it with the introduction of connectivity constraints. A new branching strategy and a primal heuristic enforcing the bounding operations have been embedded into a branch-and-cut framework. The branching rule exploits a simple valid inequality and the potential presence of necessary markets. The resulting method outperforms CPLEX 12.6 when used to solve the proposed model. The algorithms have been tested on standard TSPLIB instances, modified to include products and quantities that decrease at different rates of consumption.
MSC:
| 90C27 | Combinatorial optimization |
| 90B06 | Transportation, logistics and supply chain management |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Ahn, B.; Shin, J., Vehicle routing with time windows and time-varying congestion, J Oper Res Soc, 42, 393-400, (1991) |
| [2] | Angelelli, E.; Mansini, R.; Vindigni, M., Exploring greedy criteria for the dynamic traveling purchaser problem, Cent Eur J Oper Res, 17, 141-158, (2009) · Zbl 1204.90078 |
| [3] | Angelelli, E.; Mansini, R.; Vindigni, M., Look-ahead heuristics for the dynamic traveling purchaser problem, Comput Oper Res, 38, 1867-1876, (2011) |
| [4] | Angelelli, E.; Mansini, R.; Vindigni, M., The stochastic and dynamic traveling purchaser problem, Transp Sci, 50, 2, 642-658, (2016) |
| [5] | Beasley, J., Adapting the savings algorithm for varying inter-customer travel times, Omega, 9, 658-659, (1981) |
| [6] | Beraldi, P.; Bruni, M. E.; Manerba, D.; Mansini, R., A stochastic programming approach for the traveling purchaser problem, IMA Journal of Management Mathematics, 41-63, (2017) · Zbl 1433.90024 |
| [7] | Bianchessi, N.; Mansini, R.; Speranza, M. G., The distance constrained multiple vehicle traveling purchaser problem, Eur J Oper Res, 235, 1, 73-87, (2014) · Zbl 1305.90047 |
| [8] | Bigras, L. P.; Gamache, M.; Savard, G., The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, Discret Optim, 5, 4, 685-699, (2008) · Zbl 1152.90425 |
| [9] | Boykov, Y.; Kolmogorov, V., An experimental comparison of MIN-cut/MAX-flow algorithms for energy minimization in vision, IEEE Trans Pattern Anal Mach Intell, 26, 9, 1124-1137, (2004) |
| [10] | Burstall, R. M., A heuristic method for a job sequencing problem, Oper Res Q, 17, 291-304, (1966) |
| [11] | Buzacott, J. A.; Dutta, S. K., Sequencing many jobs on a multipurpose facility, Nav Res Logist Q, 18, 75-82, (1971) · Zbl 0217.27204 |
| [12] | Cordeau, J.-F.; Ghiani, G.; Guerriero, E., Analysis and branch-and-cut algorithm for the time-dependent travelling salesman problem, Transp Sci, 48, 46-58, (2014) |
| [13] | Eglese, R.; Maden, W.; Slater, A., A road timetabletm to aid vehicle routing and scheduling, Comput Oper Res, 33, 3508-3519, (2006) · Zbl 1094.90006 |
| [14] | Fleischmann, B.; Gnutzmann, S.; Sandvoss, E., Time-varying travel times in vehicle routing, Transp Sci, 38, 160-173, (2004) |
| [15] | Fox, K.; Gavish, B.; Graves, S., An n-constraint formulation of the (time-dependent) traveling salesman problem, Oper Res, 28, 1018-1021, (1980) · Zbl 0507.90060 |
| [16] | Gendreau, M.; Ghiani, G.; Guerriero, E., Time-dependent routing problems: a review, Comput Oper Res, 64, 189-197, (2015) · Zbl 1349.90164 |
| [17] | Ghiani, G.; Guerriero, E., A note on the ichoua, gendreau, and potvin (2003) travel time model, Transp Sci, 48, 3, 458-462, (2014) |
| [18] | Golden, B.; Levy, L.; Dahl, R., Two generalizations of the traveling salesman problem, Omega, 9, 439-455, (1981) |
| [19] | Godinho, M. T.; Gouveia, L.; Pesneau, P., Natural and extended formulations for the time-dependent traveling salesman problem, Discret Appl Math, 164, 138-153, (2014) · Zbl 1331.90066 |
| [20] | Gouveia, L.; Paias, A.; Voß, S., Models for a traveling purchaser problem with additional side-constraints, Comput Oper Res, 38, 2, 550-558, (2011) · Zbl 1231.90089 |
| [21] | Gouveia, L.; Voss, S., A classification of formulations for the (time-dependent) traveling salesman problem, Eur J Oper Res, 83, 69-82, (1995) · Zbl 0903.90170 |
| [22] | Hill, A. V.; Benton, W. C., Modelling intra-city time-dependent travel speeds for vehicle scheduling problems, J Oper Res Soc, 43, 343-351, (1992) · Zbl 0825.90358 |
| [23] | Horn, M., Efficient modeling of travel in networks with time-varying link speeds, Networks, 36, 80-90, (2000) · Zbl 0971.90009 |
| [24] | Ichoua, S.; Gendreau, M.; Potvin, J.-Y., Vehicle dispatching with time-dependent travel times, Eur J Oper Res, 144, 379-396, (2003) · Zbl 1012.90003 |
| [25] | Kuo, Y.; Wang, C.-C.; Chuang, P.-Y., Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds, Comput Ind Eng, 57, 4, 1385-1392, (2009) |
| [26] | Laporte, G.; Riera-Ledesma, J.; Salazar-González, J.-J., A branch-and-cut algorithm for the undirected traveling purchaser problem, Oper Res, 6, 940-951, (2003) · Zbl 1165.90659 |
| [27] | Letchford, A. N.; Salazar-González, J.-J., Projection results for vehicle routing, Math Program, 105, 251-274, (2006) · Zbl 1085.90032 |
| [28] | Malandraki, C.; Daskin, M. S., Time dependent vehicle routing problems: formulations, properties and solution algorithms, Transp Sci, 26, 3, 185-200, (1992) · Zbl 0758.90029 |
| [29] | Mansini, R.; Tocchella, B., The traveling purchaser problem with budget constraint, Comput Oper Res, 36, 2263-2274, (2009) · Zbl 1158.90416 |
| [30] | Picard, J.; Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Oper Res, 26, 86-110, (1978) · Zbl 0371.90066 |
| [31] | Riera-Ledesma, J.; Salazar-González, J.-J., A heuristic approach for the traveling purchaser problem, Eur J Oper Res, 162, 142-152, (2005) · Zbl 1132.90366 |
| [32] | Riera-Ledesma, J.; Salazar-González, J.-J., Solving the asymmetric traveling purchaser problem, Ann Oper Res, 144, 83-97, (2006) · Zbl 1151.90530 |
| [33] | Riera-Ledesma, J.; Salazar-González, J.-J., Solving school bus routing using the multiple vehicle traveling purchaser problem: a branch-and-cut approach, Comput Oper Res, 39, 391-404, (2012) · Zbl 1251.90061 |
| [34] | Riera-Ledesma, J.; Salazar-González, J.-J., A column generation approach for a school bus routing problem with resource constraints, Comput Oper Res, 40, 566-583, (2013) · Zbl 1349.90124 |
| [35] | Tagmouti, M.; Gendreau, M.; Potvin, J.-Y., Arc routing problems with time-dependent service costs, Eur J Oper Res, 181, 30-39, (2007) · Zbl 1121.90031 |
| [36] | Tagmouti, M.; Gendreau, M.; Potvin, J.-Y., A dynamic capacitated arc routing problem with time-dependent service costs, Transp Res Part C, 19, 20-28, (2011) |
| [37] | Vander Wiel, R. J.; Sahinidis, N. V., An exact solution approach for the time-dependent traveling-salesman problem, Nav Res Logist, 43, 797-820, (1996) · Zbl 0858.90132 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
