The Team Orienteering Pick-Up and Delivery Problem with Time Windows and its applications in fleet sizing
RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 3, pp. 503-517.

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.

Received:
Accepted:
DOI: 10.1051/ro/2015030
Classification: 68W01, 65K05, 90C06, 90C08, 90C11, 90C27, 90C29
Keywords: Pick-up and delivery problem, Team orienteering problem, Branch and Price, Vehicle Fleet Sizing
Baklagis, D. G. 1; Dikas, G. 1; Minis, I. 1

1 Design, Operations and Production Systems Lab, Department of Financial and Management Engineering, University of the Aegean, 41, Kountourioti Street, 82100 Chios, Greece.
@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, Volume 50 (2016) no. 3, pp. 503-517. doi : 10.1051/ro/2015030. http://archive.numdam.org/articles/10.1051/ro/2015030/

C. Archetti, D. Feillet, A. Hertz and M. Speranza, The capacitated team orienteering and profitable tour problems. J. Oper. Res. Soc. 60 (2009) 831–842. | DOI | Zbl

C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Vance, 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).

G. Berbeglia, J. Cordeau, I. Gribkovskaia and G. Laporte, Static pickup and delivery problems, a classification scheme and survey. TOP 15 (2007) 1–37. | DOI | MR | Zbl

S. Boussier, D. Feillet and M. Gendreau, An exact algorithm for the team orienteering problem. Oper. Res. 5 (2007) 211–230. | DOI | MR | Zbl

I. Chao, B. Golden and E. Wasil, 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

J. Desrochers, J. Desrosiers and M. Solomon, 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

G. Dikas and I. Minis, Scheduled Paratransit Transport Systems. Transp. Res. Part B 67 (2014) 18-34. | DOI

Y. Dumas, J. Desrosiers and F. Soumis, The pickup and delivery problem with time windows. Eur. J. Oper. Res. 54 (1991) 7–22. | DOI | Zbl

D. Feillet, 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

D. Feillet, P. Dejax, M. Gendreau and C. Gueguen, 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

B. Golden, L. Levy and R. Vohra, 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

M. Laumanns, L. Thiele and E. Zitzler, 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).

M. Lubbecke and J. Desrosiers, Selected Topics in Column Generation. Oper. Res. 53 (2005) 1007–1023. | DOI | MR | Zbl

S.N. Parragh, K.F. Doerner and R.F. Hartl, A survey on pickup and delivery problems. Part I, Transportation between customers and depots. J. für Betriebswirtschaft 58 (2008a) 21–51. | DOI

S.N. Parragh, K.F. Doerner and R.F. Hartl, A survey on pickup and delivery problems Part II, Transportation between pickup and delivery locations. J. für Betriebswirtschaft 58 (2008b) 81–117.

G. Righini and M. Salani, New dynamic programming algorithms for the elementary shortest path problem with resource constraints. Networks 51 (2008) 155–170. | DOI | MR | Zbl

S. Ropke and J.F. Cordeau, Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows. Transp. Sci. 43 (2009) 267–286. | DOI

J. Schonberger, H. Kopfer and D.C. Mattfeld, A combined approach to solve the pickup and delivery selection problem. Oper. Res. Proc. 2002 (2003) 150–155. | Zbl

C.K. Ting and X.L. Liao, 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

T. Tsiligirides, Heuristic methods applied to orienteering. J. Oper. Res. Soc. 37 (1984) 351–367.

P. Vansteenwegen, W. Souffruau and D. Van Oudheusden, The orienteering problem, A survey. Eur. J. Oper. Res. 209 (2011) 1–10. | DOI | MR | Zbl

Cited by Sources: