Projects

Liner Shipping Fleet Repositioning Situated at the heart of international trade, liner shipping affordably connects the economies of nations around the globe. There are over 6,900 container ships (UNCTAD'11) with a total capacity of 13.6 million TEU (Twenty-foot Equivalent Unit) (Alphaliner), and the liner shipping industry transports over $4.6 trillion worth of goods per year. (World Shipping Council)

Liner shipping networks are continuously updated to keep track of the world economy. Vessels must be regularly repositioned within the network to address these changes. Repositioning vessels constitutes a difficult operational problem in which millions of dollars are on the line. Finding good repositioning plans for vessels that include cost-saving activities such as slow-steaming, in which a vessel sails slowly to reduce its fuel consumption, are not only good for the bottom line of shipping firms, they are also good for the environment due to less CO2 output.

I am studying liner shipping fleet repositioning problems (LSFRP) for my PhD thesis. My goal is to create algorithms for solving these problems within an acceptable time for use in a decision support system. As a first step, I modeled and solved a subset of the overall repositioning problem as an automated planning problem. I conducted a comparison of techniques for solving this version of the LSFRP using the planner POPF, a mixed-integer program, and a novel method called Linear Temporal Optimization Planning along with collaborators Amanda Coles and Andrew Coles from King's College London, and master's students Christian Kroer and Adam Britt. Our work was accepted to ICAPS 2012.

For more information, see our paper "Automated Planning for Liner Shipping Fleet Repositioning", download our LSFRP PDDL instances, or look at the Linear Temporal Optimization Planning source code.

ISAC Combining GGA and Stochastic Offline Programming (Malitsky and Sellmann 2009), Instance Specific Algorithm Configuration (ISAC) takes advantage of similarities between instances of a problem to train a custom solver that adjusts its parameters based on the instance it is required to solve.

Using the "g-means" clustering algorithm (Learning the k in k-means, Hamerly and Elkan 2003), ISAC forms groups of instances from features provided by the user. GGA is then employed to find high quality parameters for a solver on those instances. Finally, when given an instance to solve, ISAC measures the distance between the instance and its learned cluster centers in order to use the solver parameters that will best solve the instance.

A paper describing the ISAC system with empirical test results was accepted to ECAI 2010.

GGA Using a novel "gender-based" genetic algorithm, GGA is a state-of-the-art parameter tuner for the automatic configuration of solvers. GGA can handle discrete, continuous and real parameters and has been used to tune solvers for a variety of problems, such as satisfiability (SAT), set covering and mixed integer programs (MIPs). GGA represents the parameters of a target solver as a "parameter tree", a type of and-or tree that expresses the relations of parameters, and exploits the tree structure during optimization.

Source code is not currently available, but binary copies of GGA can potentially be distributed. Please contact me for more information. Alternatively, you can write your own parameter tuning using the algorithm given in our 2009 CP paper.