## Abstract

A particularly difficult class of scheduling and routing problems in-

volves 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 Genera-

tion (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.

volves 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 Genera-

tion (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.

Originalsprog | Engelsk |
---|---|

Titel | Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems |

Antal sider | 17 |

Vol/bind | 7874 |

Forlag | Springer |

Publikationsdato | maj 2013 |

Sider | 111-127 |

ISBN (Trykt) | 978-3-642-38170-6 |

DOI | |

Status | Udgivet - maj 2013 |

Begivenhed | The tenth International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming - IBM T. J. Watson Research Center, Yorktown Heights(NY), USA Varighed: 18 maj 2013 → 22 maj 2013 http://www.cis.cornell.edu/ics/cpaior2013/ |

### Konference

Konference | The tenth International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming |
---|---|

Lokation | IBM T. J. Watson Research Center |

Land/Område | USA |

By | Yorktown Heights(NY) |

Periode | 18/05/2013 → 22/05/2013 |

Internetadresse |

Navn | Lecture Notes in Computer Science |
---|---|

ISSN | 0302-9743 |