CP Methods for Scheduling and Routing with Time-Dependent Task Costs
Kelareva E, Tierney K, Kilby P (2013)
In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings. Gomes C, Sellmann M (Eds); Lecture Notes in Computer Science, 7874. Berlin, Heidelberg: Springer Berlin Heidelberg: 111-127.
Sammelwerksbeitrag
| Veröffentlicht | Englisch
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Kelareva, Elena;
Tierney, KevinUniBi
;
Kilby, Philip
![](https://pub.uni-bielefeld.de/images/icon_orcid.png)
Herausgeber*in
Gomes, Carla;
Sellmann, Meinolf
Einrichtung
Abstract / Bemerkung
A particularly difficult class of scheduling and routing problems involves an objective that is a sum of time-varying action costs, which increases the size and complexity of the problem. Solve-and-improve approaches, which find an initial solution for a simplified model and improve it using a cost function, and Mixed Integer Programming (MIP) are often used for solving such problems. However, Constraint Programming (CP), particularly with Lazy Clause Generation (LCG), has been found to be faster than MIP for some scheduling problems with time-varying action costs. In this paper, we compare CP and LCG against a solve-and-improve approach for two recently introduced problems in maritime logistics with time-varying action costs: the Liner Shipping Fleet Repositioning Problem (LSFRP) and the Bulk Port Cargo Throughput Optimisation Problem (BPCTOP). We present a novel CP model for the LSFRP, which is faster than all previous methods and outperforms a simplified automated planning model without time-varying costs. We show that a LCG solver is faster for solving the BPCTOP than a standard finite domain CP solver with a simplified model. We find that CP and LCG are effective methods for solving scheduling problems, and are worth investigating for other scheduling and routing problems that are currently being solved using MIP or solve-and-improve approaches.
Erscheinungsjahr
2013
Buchtitel
Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings
Serientitel
Lecture Notes in Computer Science
Band
7874
Seite(n)
111-127
Konferenz
10th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2013)
Konferenzort
Yorktown Heights, NY, USA
Konferenzdatum
2013-05-18 – 2013-05-22
ISBN
978-3-642-38170-6
eISBN
978-3-642-38171-3
Page URI
https://pub.uni-bielefeld.de/record/2958251
Zitieren
Kelareva E, Tierney K, Kilby P. CP Methods for Scheduling and Routing with Time-Dependent Task Costs. In: Gomes C, Sellmann M, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings. Lecture Notes in Computer Science. Vol 7874. Berlin, Heidelberg: Springer Berlin Heidelberg; 2013: 111-127.
Kelareva, E., Tierney, K., & Kilby, P. (2013). CP Methods for Scheduling and Routing with Time-Dependent Task Costs. In C. Gomes & M. Sellmann (Eds.), Lecture Notes in Computer Science: Vol. 7874. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings (pp. 111-127). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-38171-3_8
Kelareva, Elena, Tierney, Kevin, and Kilby, Philip. 2013. “CP Methods for Scheduling and Routing with Time-Dependent Task Costs”. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings, ed. Carla Gomes and Meinolf Sellmann, 7874:111-127. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg.
Kelareva, E., Tierney, K., and Kilby, P. (2013). “CP Methods for Scheduling and Routing with Time-Dependent Task Costs” in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings, Gomes, C., and Sellmann, M. eds. Lecture Notes in Computer Science, vol. 7874, (Berlin, Heidelberg: Springer Berlin Heidelberg), 111-127.
Kelareva, E., Tierney, K., & Kilby, P., 2013. CP Methods for Scheduling and Routing with Time-Dependent Task Costs. In C. Gomes & M. Sellmann, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings. Lecture Notes in Computer Science. no.7874 Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 111-127.
E. Kelareva, K. Tierney, and P. Kilby, “CP Methods for Scheduling and Routing with Time-Dependent Task Costs”, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings, C. Gomes and M. Sellmann, eds., Lecture Notes in Computer Science, vol. 7874, Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp.111-127.
Kelareva, E., Tierney, K., Kilby, P.: CP Methods for Scheduling and Routing with Time-Dependent Task Costs. In: Gomes, C. and Sellmann, M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings. Lecture Notes in Computer Science. 7874, p. 111-127. Springer Berlin Heidelberg, Berlin, Heidelberg (2013).
Kelareva, Elena, Tierney, Kevin, and Kilby, Philip. “CP Methods for Scheduling and Routing with Time-Dependent Task Costs”. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings. Ed. Carla Gomes and Meinolf Sellmann. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.Vol. 7874. Lecture Notes in Computer Science. 111-127.