×

Solving a selective dial-a-ride problem with logic-based Benders decomposition. (English) Zbl 1458.90131

Summary: Today’s society is facing an ever-growing demand for mobility. To a high degree these needs can be fulfilled by individual and public transport. People that do not have access to the former and cannot use the latter require additional means of transportation. This is where dial-a-ride services come into play. The dial-a-ride problem considers transportation requests of people from pick-up to drop-off locations. Users specify time windows with respect to these points. Requests are served by a given vehicle fleet with limited capacity and tour duration per vehicle. Moreover, user inconvenience considerations are taken into account by limiting the travel time between origin and destination for each request. Previous research on the dial-a-ride problem primarily focused on serving a given set of requests with a fixed-size vehicle fleet at minimal traveling costs. It is assumed that the request set is sufficiently small to be served by the available vehicles. We consider a different scenario in which a maximal number of requests shall be served under the given constraints, i.e., it is no longer guaranteed that all requests can be accepted. For this new problem variant we propose a compact mixed integer linear programming model as well as algorithms based on Benders decomposition. In particular, we employ logic-based Benders decomposition and branch-and-check using mixed integer linear programming and constraint programming algorithms. We consider different variants on how to generate Benders cuts as well as heuristic boosting techniques and different types of valid inequalities. Computational experiments illustrate the effectiveness of the suggested algorithms.

MSC:

90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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-Oper. Res., 50, 3, 503-517, (2016) · Zbl 1352.90014
[2] Baldacci, R.; Bartolini, E.; Mingozzi, A., An exact algorithm for the pickup and delivery problem with time windows, Oper. Res., 59, 2, 414-426, (2011) · Zbl 1233.90058
[3] Baugh, jr. J. W.; Kakivaya, G. K.R.; Stone, J. R., Intractability of the dial-a-ride problem and a multiobjective solution using simulated annealing, Eng. Optim., 30, 2, 91-123, (1998)
[4] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 1, 238-252, (1962) · Zbl 0109.38302
[5] Berbeglia, G.; Pesant, G.; Rousseau, L.-M., Checking the feasibility of dial-a-ride instances using constraint programming, Transp. Sci., 45, 3, 399-412, (2011)
[6] Bodin, L. D.; Sexton, T., The multi-vehicle subscriber dial-a-ride problem, TIMS Stud. Manag. Sci., 2, 73-86, (1986)
[7] Bron, C.; Kerbosch, J., Algorithm 457: finding all cliques of an undirected graph, Commun. ACM, 16, 9, 575-577, (1973) · Zbl 0261.68018
[8] Cire, A. A.; Hooker, J. N., A heuristic logic-based benders method for the home health care problem, Technical Report, (2012), Tepper School of Business, Carnegie Mellon University
[9] Codato, G.; Fischetti, M., Combinatorial benders’ cuts for mixed-integer linear programming, Oper. Res., 54, 4, 756-766, (2006) · Zbl 1167.90601
[10] Cordeau, J.-F., A branch-and-cut algorithm for the dial-a-ride problem, Oper. Res., 54, 3, 573-586, (2006) · Zbl 1167.90681
[11] Cordeau, J.-F.; Laporte, G., The dial-a-ride problem (DARP): variants, modeling issues and algorithms, Q. J. Belgian French Italian Oper. Res. Soc., 1, 2, 89-101, (2003) · Zbl 1097.90008
[12] Cordeau, J.-F.; Laporte, G., A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Transp. Res. Part B Methodol., 37, 6, 579-594, (2003)
[13] Cordeau, J.-F.; Laporte, G., The dial-a-ride problem: models and algorithms, Ann. Oper. Res., 153, 1, 29-46, (2007) · Zbl 1157.90353
[14] Desrosiers, J.; Dumas, Y.; Soumis, F.; Taillefer, S.; Villeneuve, D., An algorithm for mini-clustering in handicapped transport, Technical Report, (1991), GERAD, HEC Montréal
[15] Dumas, Y.; Desrosiers, J.; Soumis, F., Large scale multi-vehicle dial-a-ride problems, Technical Report, (1989), GERAD, HEC Montréal
[16] Fazel-Zarandi, M. M.; Beck, J. C., Using logic-based benders decomposition to solve the capacity- and distance-constrained plant location problem, INFORMS J. Comput., 24, 3, 387-398, (2012) · Zbl 1462.90065
[17] Gansterer, M.; Küçüktepe, M.; Hartl, R. F., The multi-vehicle profitable pickup and delivery problem, OR Spectr., 39, 1, 303-319, (2017) · Zbl 1371.90024
[18] Garey, M. R.; Graham, R. L.; Johnson, D. S., Some NP-complete geometric problems, Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, 10-22, (1976), ACM New York, NY, USA · Zbl 0377.68036
[19] Garey, M. R.; Johnson, D. S., Computers and Intractability; A Guide to the Theory of NP-Completeness, (1990), W. H. Freeman & Co. New York, NY, USA
[20] Garg, M.; Smith, J. C., Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios, Omega, 36, 6, 1057-1071, (2008)
[21] Gecode Team, 2017. Gecode: generic constraint development environment. Available from http://www.gecode.org; Gecode Team, 2017. Gecode: generic constraint development environment. Available from http://www.gecode.org
[22] Geoffrion, A. M., Generalized benders decomposition, J. Optim. Theory. Appl., 10, 4, 237-260, (1972) · Zbl 0229.90024
[23] Hamdi, I.; Loukil, T., Logic-based benders decomposition to solve the permutation flowshop scheduling problem with time lags, Proceedings of the Fifth International Conference on Modeling, Simulation and Applied Optimization (ICMSAO), 1-7, (2013)
[24] Häme, L.; Hakula, H., A maximum cluster algorithm for checking the feasibility of dial-a-ride instances, Transp. Sci., 49, 2, 295-310, (2015)
[25] Hooker, J. N., 149-161, (2000), John Wiley & Sons, Inc.
[26] Hooker, J. N., Planning and scheduling by logic-based benders decomposition, Oper. Res., 55, 3, 588-602, (2007) · Zbl 1167.90512
[27] Hooker, J. N.; Ottosson, G., Logic-based benders decomposition, Math. Program., 96, 1, 33-60, (2003) · Zbl 1023.90082
[28] Ioachim, I.; Desrosiers, J.; Dumas, I.; Solomon, M. M.; Villeneuve, D., A request clustering algorithm for door-to-door handicapped transportation, Transp. Sci., 29, 1, 63-78, (1995) · Zbl 0826.90045
[29] Jain, S.; Van Hentenryck, P., Large neighborhood search for dial-a-ride problems, (Lee, J., International Conference on Principles and Practice of Constraint Programming — CP 2011, (2011), Springer, Berlin, Heidelberg), 400-413
[30] Jaw, J.-J.; Odoni, A. R.; Psaraftis, H. N.; Wilson, N. H.M., A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows, Transp. Res. Part B Methodol., 20, 3, 243-257, (1986)
[31] Paquette, J.; Bellavance, F.; Cordeau, J.-F.; Laporte, G., Measuring quality of service in dial-a-ride operations: the case of a Canadian city, Transportation, 39, 3, 539-564, (2012)
[32] Parragh, S. N.; Dörner, K. F.; Hartl, R. F., A survey on pickup and delivery models : part II: transportation between pickup and delivery locations, J. Betriebswirtschaft, 58, 81-117, (2008)
[33] Psaraftis, H. N., A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem, Transp. Sci., 14, 2, 130-154, (1980)
[34] Qiu, X.; Feuerriegel, S., A multi-vehicle profitable pickup and delivery selection problem with time windows, Proceedings of the European Conference on Information Systems (ECIS) 2014, (2014)
[35] Qiu, X.; Feuerriegel, S.; Neumann, D., Making the most of fleets: a profit-maximizing multi-vehicle pickup and delivery selection problem, Eur. J. Oper. Res., 259, 1, 155-168, (2017) · Zbl 1394.90124
[36] Raidl, G. R.; Baumhauer, T.; Hu, B., Boosting an exact logic-based benders decomposition approach by variable neighborhood search, Proceedings of the Third International Conference on Variable Neighborhood Search, 149-156, (2014), Elsevier · Zbl 1466.90057
[37] Raidl, G. R.; Baumhauer, T.; Hu, B., Speeding up logic-based benders’ decomposition by a metaheuristic for a bi-level capacitated vehicle routing problem, (Blesa, M. J.; Blum, C.; Voß, S., Hybrid Metaheuristics, Lecture Notes in Computer Science, 8457, (2014), Springer International Publishing), 183-197
[38] Ropke, S.; Cordeau, J.-F., Branch and cut and price for the pickup and delivery problem with time windows, Transp. Sci., 43, 3, 267-286, (2009)
[39] Ropke, S.; Cordeau, J.-F.; Laporte, G., Models and branch-and-cut algorithms for pickup and delivery problems with time windows, Networks, 49, 4, 258-272, (2007) · Zbl 1141.90340
[40] Sexton, T. R.; Bodin, L. D., Optimizing single vehicle many-to-many operations with desired delivery times: I. scheduling, Transp. Sci., 19, 4, 378-410, (1985) · Zbl 0608.90043
[41] Sexton, T. R.; Bodin, L. D., Optimizing single vehicle many-to-many operations with desired delivery times: II. routing, Transp. Sci., 19, 4, 411-435, (1985) · Zbl 0618.90042
[42] Thorsteinsson, E. S., Branch-and-check: a hybrid framework integrating mixed integer programming and constraint logic programming, Principles and Practice of Constraint Programming — CP 2001, 16-30, (2001), Springer · Zbl 1067.68677
[43] Tran, T. T.; Beck, J. C., Logic-based benders decomposition for alternative resource scheduling with sequence dependent setups, Proceedings of the Twentieth European Conference on Artificial Intelligence, 774-779, (2012), IOS Press Amsterdam, The Netherlands · Zbl 1327.90075
[44] Wheatley, D.; Gzara, F.; Jewkes, E., Logic-based benders decomposition for an inventory-location problem with service constraints, Omega, 55, 10-23, (2015)
[45] Wolfler Calvo, R.; Colorni, A., An effective and fast heuristic for the dial-a-ride problem, 4OR, 5, 1, 61-73, (2007) · Zbl 1121.90019
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.