The risk-averse traveling repairman problem with profits. (English) Zbl 1418.90066
Summary: In this paper, we study a stochastic variant of the traveling repairman problem with profits in which travel times are random. The introduction of the arrival time in the objective function instead of the travel time, which is common in most vehicle routing problems, poses compelling challenges, emphasized by the incorporation of the stochasticity in travel times and by the presence of profits. A risk-averse perspective is considered in the model, which is then formulated as a nonlinear integer model and heuristically solved by means of a beam search heuristic. Experimental results have been performed on instances adapted from the available deterministic datasets, to show the effectiveness of the solution approach.
MSC:
| 90B15 | Stochastic network models in operations research |
References:
| [1] | Adulyasak Y, Jaillet P (2014) Models and algorithms for stochastic and robust vehicle routing with deadlines. Transp Sci 50(2):608-626 |
| [2] | Agra A, Christiansen M, Hvattum LM, Figueiredo R, Poss M, Requejo C (2012) Layered formulation for the robust vehicle routing problem with time windows. Lect Notes Comput Sci 7422:249-260 · Zbl 1370.90019 |
| [3] | Agra A, Christiansen M, Hvattum LM, Figueiredo R, Poss M, Requejo C (2013) The robust vehicle routing problem with time windows. Comput Oper Res 40(3):856-866 · Zbl 1349.90152 |
| [4] | Ando N, Taniguchi E (2006) Travel time reliability in vehicle routing and scheduling with time windows. Netw Spat Econ 6(3-4):293-311 · Zbl 1128.90308 |
| [5] | Araya I, Riff MC (2014) A beam search approach to the container loading problem. Comput Oper Res 43:100-107 · Zbl 1348.90532 |
| [6] | Ausiello G, Leonardi S, Marchetti-Spaccamela A (1994) On salesman repairmen spiders and other traveling agents. In: Proceeding of the Italian conference on algorithms and complexity, pp 1-16 · Zbl 0973.90082 |
| [7] | Baldi MM, Crainic TG, Perboli G, Tadei R (2014) Branch and price and beam search algorithms for the variable cost and size bin packing problem with optional items. Ann Oper Res 222(1):125-141 · Zbl 1303.90085 |
| [8] | Beraldi P, Bruni ME (2010) An exact approach for solving integer problem under probabilistic constraints with random technology matrix. Ann Oper Res 177(1):127-137 · Zbl 1195.90066 |
| [9] | Beraldi P, Ruszczyński A (2002a) A branch and bound method for stochastic integer problems under probabilistic constraints. Optim Methods Softw 17:359-382 · Zbl 1064.90030 |
| [10] | Beraldi P, Ruszczyński A (2002b) The probabilistic set-covering problem. Oper Res 50(6):956-967 · Zbl 1163.90655 |
| [11] | Beraldi P, Ruszczyński A (2005) Beam search heuristic to solve stochastic integer problems under probabilistic constraints. Eur J Oper Res 167(1):35-47 · Zbl 1074.90031 |
| [12] | Beraldi P, Ghiani G, Laporte G, Musmanno R (2005) Efficient neighborhood search for the probabilistic pickup and delivery travelling salesman problem. Networks 45(4):195-198 · Zbl 1068.90085 |
| [13] | Beraldi P, Bruni ME, Violi A (2012) Capital rationing problems under uncertainty and risk. Comput Optim Appl 51(3):1375-1396 · Zbl 1241.90064 |
| [14] | Beraldi P, Bruni ME, Laganà D, Musmanno R (2015) The mixed capacitated general routing problem under uncertainty. Eur J Oper Res 240(2):382-392 · Zbl 1357.90012 |
| [15] | Beraldi P, Bruni ME, Manerba D, Mansini R (2017) A stochastic programming approach for the traveling purchaser problem. IMA J Manag Math 28(1):41-63 · Zbl 1433.90024 |
| [16] | Bigras LP, Gamache M, Savard G (2008) The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Discrete Optim 5(4):685-699 · Zbl 1152.90425 |
| [17] | Birge J, Louveaux F (1997) Introduction to stochastic programming. Springer, Berlin · Zbl 0892.90142 |
| [18] | Birgin EG, Ferreira JE, Ronconi DP (2015) List scheduling and beam search methods for the flexible job shop scheduling problem with sequencing flexibility. Eur J Oper Res 247(2):421-440 · Zbl 1346.90328 |
| [19] | Blum C, Miralles C (2011) On solving the assembly lineworker assignment and balancing problem via beam search. Comput Oper Res 38:328-339 · Zbl 1231.90256 |
| [20] | Bock S (2015) Solving the traveling repair problem on a line with general processing times and deadlines. Eur J Oper Res 24(3):690-703 · Zbl 1346.90692 |
| [21] | Bruni ME, Beraldi P, Laganà D (2013) The express heuristic for probabilistically constrained integer problems. J Heuristics 19(3):423-441 |
| [22] | Bruni ME, Guerriero F, Beraldi P (2014) Designing robust routes for demand-responsive transport systems. Transp Res Part E Logist Transp Rev 70:1-16 |
| [23] | Bruni ME, Beraldi P, Khodaparasti S (2018) A heuristic approach for the k-traveling repairman problem with profits under uncertainty. Electron Notes Discrete Math 69:221-228 |
| [24] | Bruni ME, Beraldi P, Khodaparasti S (2018) A fast heuristic for routing in post-disaster humanitarian relief logistics. Transp Res Procedia 30:304-313 |
| [25] | Caceres H, Hwang H, He Q (2016) Estimating freeway route travel time distributions with consideration to time-of-day, inclement weather, and traffic incidents. J Adv Transp 50:967-987 |
| [26] | Calafiore G, El Ghaoui L (2006) On distributionally robust chance-constrained linear programs. J Optim Theory Appl 130(1):1-22 · Zbl 1143.90021 |
| [27] | Campbell A, Vandenbussche D, Hermann W (2008) Routing for relief efforts. Transp Sci 42(2):127-145 |
| [28] | Dewilde T, Cattrysse D, Coene S, Spieksma FCR, Vansteenwegen P (2013) Heuristics for the traveling repairman problem with profits. Comput Oper Res 40(7):1700-1707 · Zbl 1348.90634 |
| [29] | Fang KT, Kotz S, Ng KW (1990) Symmetric multivariate and related distributions. Chapman & Hall, London. ISBN: 9781315897943 · Zbl 0699.62048 |
| [30] | Fernandez-Viagas V, Framinan JM (2017) A beam-search-based constructive heuristic for the PFSP to minimise total flowtime. Comput Oper Res 81:167-177 · Zbl 1391.90260 |
| [31] | Fischetti M, Laporte G, Martello S (1993) The delivery man problem and cumulative matroids. Oper Res 41(6):1055-1064 · Zbl 0791.90062 |
| [32] | Gomez A, Marino R, Akhavan-Tabatabaei R, Medaglia AL, Mendoza JE (2016) On modeling stochastic travel and service times in vehicle routing. Transp Sci 50(2):627-641 |
| [33] | Henrion R, Strugarek C (2008) Convexity of chance constraints with independent random variables. Comput Optim Appl 412(2):263-276 · Zbl 1168.90568 |
| [34] | Jaillet P, Qi J, Sim M (2016) Routing optimization under uncertainty. Oper Res 64(1):186-200 · Zbl 1338.90107 |
| [35] | Jung S, Haghani A (2001) Genetic algorithm for the time-dependent vehicle routing problem. Transp Res Rec J Transp Res Board 1771(1):164-171 |
| [36] | Kenyon A, Morton D (2003) Stochastic vehicle routing with random travel times. Transp Sci 37(1):69-82 |
| [37] | Khokhlov V (2016) Conditional value at risk for elliptical distributions. Evropsky Casopis Ekonomiky a Managementu 2(6):70-79 |
| [38] | Krokhmal P, Zabarankin M, Uryasev S (2011) Modeling and optimization of risk. Surv Oper Res Manag Sci 16(2):49-66 |
| [39] | Laporte G, Louveaux F, Mercure H (1992) The vehicle routing problem with stochastic travel times. Transp Sci 26(3):161-70 · Zbl 0761.90035 |
| [40] | Lecluyse C, Van Woensel T, Peremans H (2009) Vehicle routing with stochastic time-dependent travel times. 4OR-Q J Oper Res 7:363-377 · Zbl 1188.90032 |
| [41] | Lee C, Lee K, Park S (2004) Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J Oper Res Soc 63(9):1294-306 |
| [42] | Li X, Stephen PT, Leung CH (2010) Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm. Int J Prod Econ 125(1):137-145 |
| [43] | Lucena A (1990) Time-dependent traveling salesman problem—the deliveryman case. Networks 20(6):753-763 · Zbl 0744.90063 |
| [44] | Maggioni F, Perboli G, Tadei R (2014) The multi-path traveling salesman problem with stochastic travel costs: building realistic instances for city logistics applications. Transp Res Procedia 3:528-536 |
| [45] | Oyola J, Arntzen H, Woodruff DL (2017) The stochastic vehicle routing problem, a literature review, part II: solution methods. EURO J Transp Logist 6(4):349-388 |
| [46] | Oyola J, Arntzen H, Woodruff DL (2018) The stochastic vehicle routing problem, a literature review, part I: models. EURO J Transp Logist 7(3):193-221 |
| [47] | Perboli G, Gobbato L, Maggioni F (2017) A progressive hedging method for the multi-path traveling salesman problem with stochastic travel times. IMA J Manag Math 28(1):65-86 · Zbl 1433.90143 |
| [48] | Solano-Charris EL, Prins C, Santos AC (2016) Solving the bi-objective robust vehicle routing problem with uncertain costs and demands. RAIRO Oper Res 50(4-5):689-714 · Zbl 1353.90006 |
| [49] | Sungur I, Ordóñez F, Dessouky M (2008) A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans 40(5):509-523 |
| [50] | Susilawati S, Taylor M, Somenahalli S (2013) Distributions of travel time variability on urban roads. J Adv Transp 47(8):720-736 |
| [51] | Taş D, Dellaert N, Van Woensel T, de Kok AG (2013) Vehicle routing problem with stochastic travel times including soft time windows and service costs. Comput Oper Res 40(1):214-224 · Zbl 1349.90131 |
| [52] | Taş D, Gendreau M, Dellaert N, Van Woensel T, de Kok AG (2014) Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach. Eur J Oper Res 236(3):789-799 · Zbl 1304.90044 |
| [53] | Tulabandhula T, Rudin C, Jaillet P (2011) The machine learning and traveling repairman problem. Algorithm Decis Theory Lect Notes Comput Sci 6992:262-276 · Zbl 1233.90073 |
| [54] | Yavuz M (2017) An iterated beam search algorithm for the green vehicle routing problem. Networks 69(3):317-328 |
| [55] | Zhang T, Chaovalitwongse WA, Zhang Y (2012) Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries. Comput Oper Res 39(10):2277-2290 · Zbl 1251.90065 |
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.
