research-article

The Traveling Purchaser Problem with time-dependent quantities

Authors:

M. VindigniAuthors Info & Claims

Computers and Operations Research, Volume 82, Issue C

Pages 15 - 26

https://doi.org/10.1016/j.cor.2017.01.001

Published: 01 June 2017 Publication History

Abstract

A novel time dependent version of the Traveling Purchaser Problem is presented.A LP model introducing constrains to represent dynamically changing quantities is defined.An exact method based on a branch-and-cut algorithm exploiting the structure of the problem is described.Experiments over a wide set of instances show the efficacy of the proposed approach. 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.

References

[1]

B. Ahn, J. Shin, Vehicle routing with time windows and time-varying congestion, J Oper Res Soc, 42 (1991) 393-400.

[2]

E. Angelelli, R. Mansini, M. Vindigni, Exploring greedy criteria for the dynamic traveling purchaser problem, Cent Eur J Oper Res, 17 (2009) 141-158.

[3]

E. Angelelli, R. Mansini, M. Vindigni, Look-ahead heuristics for the dynamic traveling purchaser problem, Comput Oper Res, 38 (2011) 1867-1876.

Digital Library

[4]

E. Angelelli, R. Mansini, M. Vindigni, The stochastic and dynamic traveling purchaser problem, Transp Sci, 50 (2016) 642-658.

[5]

J. Beasley, Adapting the savings algorithm for varying inter-customer travel times, Omega, 9 (1981) 658-659.

[6]

P. Beraldi, M.E. Bruni, D. Manerba, R. Mansini, A stochastic programming approach for the traveling purchaser problem, IMA Journal of Management Mathematics (2017) 41-63.

[7]

N. Bianchessi, R. Mansini, M.G. Speranza, The distance constrained multiple vehicle traveling purchaser problem, Eur J Oper Res, 235 (2014) 73-87.

[8]

L.P. Bigras, M. Gamache, G. Savard, The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, Discret Optim, 5 (2008) 685-699.

Digital Library

[9]

Y. Boykov, V. Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, IEEE Trans Pattern Anal Mach Intell, 26 (2004) 1124-1137.

Digital Library

[10]

R.M. Burstall, A heuristic method for a job sequencing problem, Oper Res Q, 17 (1966) 291-304.

[11]

J.A. Buzacott, S.K. Dutta, Sequencing many jobs on a multipurpose facility, Nav Res Logist Q, 18 (1971) 75-82.

[12]

J.-F. Cordeau, G. Ghiani, E. Guerriero, Analysis and branch-and-cut algorithm for the time-dependent travelling salesman problem, Transp Sci, 48 (2014) 46-58.

Digital Library

[13]

R. Eglese, W. Maden, A. Slater, A road timetabletm to aid vehicle routing and scheduling, Comput Oper Res, 33 (2006) 3508-3519.

Digital Library

[14]

B. Fleischmann, S. Gnutzmann, E. Sandvoss, Time-varying travel times in vehicle routing, Transp Sci, 38 (2004) 160-173.

Digital Library

[15]

K. Fox, B. Gavish, S. Graves, An n-constraint formulation of the (time-dependent) traveling salesman problem, Oper Res, 28 (1980) 1018-1021.

Digital Library

[16]

M. Gendreau, G. Ghiani, E. Guerriero, Time-dependent routing problems: a review, Comput Oper Res, 64 (2015) 189-197.

Digital Library

[17]

G. Ghiani, E. Guerriero, A note on the ichoua, gendreau, and potvin (2003) travel time model, Transp Sci, 48 (2014) 458-462.

Digital Library

[18]

B. Golden, L. Levy, R. Dahl, Two generalizations of the traveling salesman problem, Omega, 9 (1981) 439-455.

[19]

M.T. Godinho, L. Gouveia, P. Pesneau, Natural and extended formulations for the time-dependent traveling salesman problem, Discret Appl Math, 164 (2014) 138-153.

Digital Library

[20]

L. Gouveia, A. Paias, S. Vo, Models for a traveling purchaser problem with additional side-constraints, Comput Oper Res, 38 (2011) 550-558.

Digital Library

[21]

L. Gouveia, S. Voss, A classification of formulations for the (time-dependent) traveling salesman problem, Eur J Oper Res, 83 (1995) 69-82.

[22]

A.V. Hill, W.C. Benton, Modelling intra-city time-dependent travel speeds for vehicle scheduling problems, J Oper Res Soc, 43 (1992) 343-351.

[23]

M. Horn, Efficient modeling of travel in networks with time-varying link speeds, Networks, 36 (2000) 80-90.

[24]

S. Ichoua, M. Gendreau, J.-Y. Potvin, Vehicle dispatching with time-dependent travel times, Eur J Oper Res, 144 (2003) 379-396.

[25]

Y. Kuo, C.-C. Wang, P.-Y. Chuang, Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds, Comput Ind Eng, 57 (2009) 1385-1392.

Digital Library

[26]

G. Laporte, J. Riera-Ledesma, J.-J. Salazar-Gonzlez, A branch-and-cut algorithm for the undirected traveling purchaser problem, Oper Res, 6 (2003) 940-951.

Digital Library

[27]

A.N. Letchford, J.-J. Salazar-Gonzlez, Projection results for vehicle routing, Math Program, 105 (2006) 251-274.

[28]

C. Malandraki, M.S. Daskin, Time dependent vehicle routing problems: formulations, properties and solution algorithms, Transp Sci, 26 (1992) 185-200.

Digital Library

[29]

R. Mansini, B. Tocchella, The traveling purchaser problem with budget constraint, Comput Oper Res, 36 (2009) 2263-2274.

Digital Library

[30]

J. Picard, M. Queyranne, The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Oper Res, 26 (1978) 86-110.

Digital Library

[31]

J. Riera-Ledesma, J.-J. Salazar-Gonzlez, A heuristic approach for the traveling purchaser problem, Eur J Oper Res, 162 (2005) 142-152.

[32]

J. Riera-Ledesma, J.-J. Salazar-Gonzlez, Solving the asymmetric traveling purchaser problem, Ann Oper Res, 144 (2006) 83-97.

[33]

J. Riera-Ledesma, J.-J. Salazar-Gonzlez, Solving school bus routing using the multiple vehicle traveling purchaser problem: a branch-and-cut approach, Comput Oper Res, 39 (2012) 391-404.

Digital Library

[34]

J. Riera-Ledesma, J.-J. Salazar-Gonzlez, A column generation approach for a school bus routing problem with resource constraints, Comput Oper Res, 40 (2013) 566-583.

Digital Library

[35]

M. Tagmouti, M. Gendreau, J.-Y. Potvin, Arc routing problems with time-dependent service costs, Eur J Oper Res, 181 (2007) 30-39.

[36]

M. Tagmouti, M. Gendreau, J.-Y. Potvin, A dynamic capacitated arc routing problem with time-dependent service costs, Transp Res Part C, 19 (2011) 20-28.

[37]

R.J. Vander Wiel, N.V. Sahinidis, An exact solution approach for the time-dependent traveling-salesman problem, Nav Res Logist, 43 (1996) 797-820.

Cited By

Canca DBarrena ELaporte G(2024)Arrival and service time dependencies in the single- and multi-visit selective traveling salesman problemComputers and Operations Research10.1016/j.cor.2024.106632166:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.cor.2024.106632
Kucukoglu IVansteenwegen PCattrysse D(2024)The traveling purchaser problem for perishable foodsComputers and Industrial Engineering10.1016/j.cie.2024.110424195:COnline publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1016/j.cie.2024.110424
Roy AMaity SMoon I(2023)Multi-vehicle clustered traveling purchaser problem using a variable-length genetic algorithmEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106351123:PBOnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.106351
Show More Cited By

The Traveling Purchaser Problem with time-dependent quantities

Recommendations

Models for a traveling purchaser problem with additional side-constraints

The traveling purchaser problem (TPP) is the problem of determining a tour of a purchaser that needs to buy several items in different shops such that the total amount of travel and purchase costs is minimized. Motivated by an application in machine ...
A branch-and-cut algorithm for the multi-vehicle traveling purchaser problem with pairwise incompatibility constraints

We introduce a problem where a fleet of vehicles is available to visit suppliers offering various products at different prices and quantities, with the aim to select a subset of suppliers so to satisfy products demand at the minimum traveling and ...
The traveling purchaser problem, with multiple stacks and deliveries: A branch-and-cut approach

The Double Traveling Salesman Problem with Multiple Stacks is a pickup-and-delivery single-vehicle routing problem which performs all pickup operations before the deliveries. The vehicle has a loading space divided into stacks of a fixed height that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 82, Issue C

June 2017

180 pages

ISSN:0305-0548

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 June 2017

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Canca DBarrena ELaporte G(2024)Arrival and service time dependencies in the single- and multi-visit selective traveling salesman problemComputers and Operations Research10.1016/j.cor.2024.106632166:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.cor.2024.106632
Kucukoglu IVansteenwegen PCattrysse D(2024)The traveling purchaser problem for perishable foodsComputers and Industrial Engineering10.1016/j.cie.2024.110424195:COnline publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1016/j.cie.2024.110424
Roy AMaity SMoon I(2023)Multi-vehicle clustered traveling purchaser problem using a variable-length genetic algorithmEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.106351123:PBOnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.engappai.2023.106351
Kucukoglu I(2022)The traveling purchaser problem with fast service optionComputers and Operations Research10.1016/j.cor.2022.105700141:COnline publication date: 9-May-2022
https://dl.acm.org/doi/10.1016/j.cor.2022.105700
Xiao MZhang JLin W(2022)Parameterized algorithms and complexity for the traveling purchaser problem and its variantsJournal of Combinatorial Optimization10.1007/s10878-020-00608-x44:4(2269-2285)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10878-020-00608-x

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents