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

    Abstract

    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 Sep 200925 Sep 2009
    Conference number: 21st

    Conference

    ConferenceEuropean Modeling and Simulation Symposium 2009
    Abbreviated titleEMSS 2009
    CountrySpain
    CityPuerto de la Cruz
    Period23/09/0925/09/09

    Keywords

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

    Cite this

    Guimarans, D., Ramos, J. J., Wallace, M., & Riera, D. (2009). A hybrid constraint programming / local search approach to the pick-up and delivery problem with time windows. In 21st European Modeling and Simulation Symposium, EMSS 2009
    Guimarans, Daniel ; Ramos, Juan José ; Wallace, Mark ; Riera, Daniel. / A hybrid constraint programming / local search approach to the pick-up and delivery problem with time windows. 21st European Modeling and Simulation Symposium, EMSS 2009. 2009.
    @inproceedings{fa19ff796c6b4c7788fb8262fe388880,
    title = "A hybrid constraint programming / local search approach to the pick-up and delivery problem with time windows",
    abstract = "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.",
    keywords = "Constraint programming, Hybrid algorithm, Local search, Pick up and delivery problem",
    author = "Daniel Guimarans and Ramos, {Juan Jos{\'e}} and Mark Wallace and Daniel Riera",
    year = "2009",
    language = "English",
    booktitle = "21st European Modeling and Simulation Symposium, EMSS 2009",

    }

    Guimarans, D, Ramos, JJ, Wallace, M & Riera, D 2009, A hybrid constraint programming / local search approach to the pick-up and delivery problem with time windows. in 21st European Modeling and Simulation Symposium, EMSS 2009. European Modeling and Simulation Symposium 2009, Puerto de la Cruz, Spain, 23/09/09.

    A hybrid constraint programming / local search approach to the pick-up and delivery problem with time windows. / Guimarans, Daniel; Ramos, Juan José; Wallace, Mark; Riera, Daniel.

    21st European Modeling and Simulation Symposium, EMSS 2009. 2009.

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

    TY - GEN

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

    AU - Guimarans, Daniel

    AU - Ramos, Juan José

    AU - Wallace, Mark

    AU - Riera, Daniel

    PY - 2009

    Y1 - 2009

    N2 - 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.

    AB - 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.

    KW - Constraint programming

    KW - Hybrid algorithm

    KW - Local search

    KW - Pick up and delivery problem

    UR - http://www.scopus.com/inward/record.url?scp=84874130715&partnerID=8YFLogxK

    M3 - Conference Paper

    BT - 21st European Modeling and Simulation Symposium, EMSS 2009

    ER -

    Guimarans D, Ramos JJ, Wallace M, Riera D. A hybrid constraint programming / local search approach to the pick-up and delivery problem with time windows. In 21st European Modeling and Simulation Symposium, EMSS 2009. 2009