A hybrid constraint programming / local search approach to the pick-up and delivery problem with time windows

Daniel Guimarans, Juan José Ramos, Mark Wallace, Daniel Riera

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


    Routing vehicles to serve customers is a problem that naturally arises in many distribution systems. Moreover, fleet management requires fast algorithms able to cope with continuously changing needs. Many efforts have been addressed to tackle different vehicle routing problem's variants. Among them, the pick up and delivery problem with time windows (PDTW) has received far less attention despite its relevance from practical and theoretical perspectives. The present paper provides a hybrid approach to the PDTW based on Constraint Programming paradigm and local search. Indeed, the proposed algorithm includes some performance improvements to enhance its efficiency. Thus, this hybrid approach may provide a solution to problems otherwise intractable in a reasonable computational time, as shown in the presented results. Due to these characteristics, the proposed algorithm may be an efficient tool in decision making support, as well as a mechanism able to provide an initial solution for subsequent optimization techniques.

    Original languageEnglish
    Title of host publication21st European Modeling and Simulation Symposium, EMSS 2009
    Publication statusPublished - 2009
    EventEuropean Modeling and Simulation Symposium 2009 - Puerto de la Cruz, Spain
    Duration: 23 Sept 200925 Sept 2009
    Conference number: 21st


    ConferenceEuropean Modeling and Simulation Symposium 2009
    Abbreviated titleEMSS 2009
    CityPuerto de la Cruz


    • Constraint programming
    • Hybrid algorithm
    • Local search
    • Pick up and delivery problem

    Cite this