In this paper we consider the problem of prioritized pick-up and delivery operations under resource constraints. Our proposed formulation combines the Team Orienteering Problem with the case of Pick-up and Delivery with Time Windows and Capacity Constraints. We solved this model to optimality using an exact Branch-and-Price method, which is based on previous work. To study the performance of the solution method and its refinements, we conducted extensive computational experiments. We also applied the proposed model and method to a relevant logistic system and investigated its performance under various conditions. Finally, we present a practical method to determine the most suitable fleet configuration for a pick-up and delivery system that delivers prioritized operations to a known client base.
Accepté le :
DOI : 10.1051/ro/2015030
Mots-clés : Pick-up and delivery problem, Team orienteering problem, Branch and Price, Vehicle Fleet Sizing
@article{RO_2016__50_3_503_0,
author = {Baklagis, D. G. and Dikas, G. and Minis, I.},
title = {The {Team} {Orienteering} {Pick-Up} and {Delivery} {Problem} with {Time} {Windows} and its applications in fleet sizing},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {503--517},
publisher = {EDP-Sciences},
volume = {50},
number = {3},
year = {2016},
doi = {10.1051/ro/2015030},
mrnumber = {3519330},
zbl = {1352.90014},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2015030/}
}
TY - JOUR AU - Baklagis, D. G. AU - Dikas, G. AU - Minis, I. TI - The Team Orienteering Pick-Up and Delivery Problem with Time Windows and its applications in fleet sizing JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 503 EP - 517 VL - 50 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2015030/ DO - 10.1051/ro/2015030 LA - en ID - RO_2016__50_3_503_0 ER -
%0 Journal Article %A Baklagis, D. G. %A Dikas, G. %A Minis, I. %T The Team Orienteering Pick-Up and Delivery Problem with Time Windows and its applications in fleet sizing %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 503-517 %V 50 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2015030/ %R 10.1051/ro/2015030 %G en %F RO_2016__50_3_503_0
Baklagis, D. G.; Dikas, G.; Minis, I. The Team Orienteering Pick-Up and Delivery Problem with Time Windows and its applications in fleet sizing. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 3, pp. 503-517. doi : 10.1051/ro/2015030. http://archive.numdam.org/articles/10.1051/ro/2015030/
, , and , The capacitated team orienteering and profitable tour problems. J. Oper. Res. Soc. 60 (2009) 831–842. | DOI | Zbl
, , , and , Branch-and-price, Column generation for solving huge integer programs. Oper. Res. 46 (1998) 316–329. | DOI | MR | Zbl
Benchmark Instances for: TOPDPTW and applications in fleet sizing. Retrieved from: http://labs.fme.aegean.gr/deopsys/topptw˙instances (2014).
, , and , Static pickup and delivery problems, a classification scheme and survey. TOP 15 (2007) 1–37. | DOI | MR | Zbl
, and , An exact algorithm for the team orienteering problem. Oper. Res. 5 (2007) 211–230. | DOI | MR | Zbl
, and , The team orienteering problem. Eur. J. Oper. Res. 88 (1996) 464–474. | DOI | Zbl
G. Desaulniers, J. Desrosiers, I. Ioachim, M. Solomon, F. Soumis and D. Villeneuve, A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems. Fleet Management and Logistics, edited by T.G. Crainic and G. Laporte. Kluwer, Norwell, MA (1998) 57–93. | Zbl
G. Desaulniers, J. Desrosiers and M. Solomon, Column Generation. Springer Science and Business Media, Inc., New York (2005). | MR | Zbl
, and , A new optimization algorithm for the vehicle routing prolem with time windows. Oper. Res. 40 (1992) 342–354. | DOI | MR | Zbl
J. Desrosiers, M. Dumas, M. Solomon and F. Soumis, Time Constrained Routing and Scheduling. Handbooks in Operations Research and Management Science, 8: Network Routing, edited by M. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser. North-holland, Amsterdam (1995) 35–139. | MR | Zbl
and , Scheduled Paratransit Transport Systems. Transp. Res. Part B 67 (2014) 18-34. | DOI
, and , The pickup and delivery problem with time windows. Eur. J. Oper. Res. 54 (1991) 7–22. | DOI | Zbl
, A tutorial on column generation and branch-and-price for the vehicle routing problems. 4OR: A Quarterly J. Oper. Res. 8 (2010) 407–424. | DOI | MR | Zbl
, , and , An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints, Application to Some Vehicle Routing Problem. Networks 44 (2004) 217–229. | DOI | MR | Zbl
, and , The orienteering problem. Naval Res. Logistics 34 (1987) 307–318. | DOI | Zbl
W. Harvey and M. Ginsberg, Limited Discrepancy Search. Proc. of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal Québec, Canada. Morgan Kaufmann Publishers Inc. (1995) 607–615.
S. Irnich and G. Desaulniers, Shortest Path Problems with Resource Constraints. In Column Generation, edited by G. Desaulniers, J. Desrosiers and M.M. Solomon. Springer (2005) 33–65. | Zbl
, and , An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur. J. Oper. Res. 169 (2006) 932–942. | DOI | MR | Zbl
H. Li and A. Lim, A MetaHeuristic for the Pickup and Delivery Problem with Time Windows. In 13th International Conference on Tools with Artificial Intelligence, Dallas (2001).
and , Selected Topics in Column Generation. Oper. Res. 53 (2005) 1007–1023. | DOI | MR | Zbl
, and , A survey on pickup and delivery problems. Part I, Transportation between customers and depots. J. für Betriebswirtschaft 58 (2008a) 21–51. | DOI
, and , A survey on pickup and delivery problems Part II, Transportation between pickup and delivery locations. J. für Betriebswirtschaft 58 (2008b) 81–117.
and , New dynamic programming algorithms for the elementary shortest path problem with resource constraints. Networks 51 (2008) 155–170. | DOI | MR | Zbl
and , Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows. Transp. Sci. 43 (2009) 267–286. | DOI
, and , A combined approach to solve the pickup and delivery selection problem. Oper. Res. Proc. 2002 (2003) 150–155. | Zbl
and , The selective pickup and delivery problem: Formulation and a memetic algorithm. Int. J. Prod. Econ. 141 (2013) 199–211. | DOI
P. Toth and D. Vigo, The Vehicle Routing Problem, SIAM Monogr. Discr. Math. Appl. Philadelphia (2002). | MR
, Heuristic methods applied to orienteering. J. Oper. Res. Soc. 37 (1984) 351–367.
, and , The orienteering problem, A survey. Eur. J. Oper. Res. 209 (2011) 1–10. | DOI | MR | Zbl
Cité par Sources :
