Feasibility of the Pickup and Delivery Problem with Fixed Partial Routes: A Complexity Analysis

References

• Abdel-Wahab H. M. Scheduling with applications to register allocation and deadlock problems. (1976) . Ph.D. thesis, University of Waterloo, CanadaGoogle Scholar
• Apt K.Principles of Constraint Programming (2003) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Berbeglia G., Pesant G., Rousseau L.-M. Checking feasibility of dial-a-ride instances using constraint programming. Transportation Sci. (2011) 45(3):399–412Link, Google Scholar
• Berbeglia G., Cordeau J.-F., Gribkovskaia I., Laporte G. Static pickup and delivery problems: A classification scheme and survey. TOP (2007) 15(1):1–31Crossref, Google Scholar
• Cordeau J.-F., Laporte G. The dial-a-ride problem: Models and algorithms. Ann. Oper. Res. (2007) 153(1):29–46Crossref, Google Scholar
• De Backer B., Furnon V., Shaw P., Kilby P., Prosser P. Vehicle routing problems using constraint programming and metaheuristics. J. Heuristics (2000) 6(4):501–523Crossref, Google Scholar
• Ghiani G., Laporte G., Semet F. The black and white traveling salesman problem. Oper. Res. (2006) 54(2):366–378Link, Google Scholar
• Hernández-Pérez H., Salazar-González J. J., Junger M., Reinelt G., Rinaldi G. The one-commodity pickup-and-delivery traveling salesman problem. Eureka, You Shrink! (2003) 2570(Springer, New York) 89–104Lecture Notes in Computer ScienceCrossref, Google Scholar
• Mascis A., Pacciarelli D. Job-shop scheduling with blocking and no-wait constraints. Eur. J. Oper. Res. (2002) 143(3):498–517Crossref, Google Scholar
• Meloni C., Pacciarelli D., Pranzo M. A rollout metaheuristic for job scheduling problems. Ann. Oper. Res. (2004) 131(1–4):215–235Crossref, Google Scholar
• Moore J. M. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Sci. (1968) 15(1):102–109Link, Google Scholar
• Mosheiov G. The traveling salesman problem with pick-up and delivery. Eur. J. Oper. Res. (1994) 79(2):299–310Crossref, Google Scholar
• Parragh S. N., Doerner K. F., Hartl R. F. A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations. J. für Betriebswirtschaft (2008) 58(2):81–117Crossref, Google Scholar
• Savelsbergh M. W. P. Local search in routing problems with time windows. Ann. Oper. Res. (1985) 4(1):285–305Crossref, Google Scholar
• Sethi R. Complete register allocation problems. Proc. Fifth Annual ACM Sympos. Theory Comput. (1973) (ACM, Austin, TX) 182–195Google Scholar