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 language | English |
|---|---|
| Title of host publication | 21st European Modeling and Simulation Symposium, EMSS 2009 |
| Publication status | Published - 2009 |
| Event | European Modeling and Simulation Symposium 2009 - Puerto de la Cruz, Spain Duration: 23 Sep 2009 → 25 Sep 2009 Conference number: 21st |
Conference
| Conference | European Modeling and Simulation Symposium 2009 |
|---|---|
| Abbreviated title | EMSS 2009 |
| Country | Spain |
| City | Puerto de la Cruz |
| Period | 23/09/09 → 25/09/09 |
Keywords
- Constraint programming
- Hybrid algorithm
- Local search
- Pick up and delivery problem
Cite this
}
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 proceeding › Conference Paper › Research › peer-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 -