The Maritime Pickup and Delivery Problem with Cost and Time Window Constraints : System Modeling and A* Based Solution

Abstract

In the ship chartering business, more and more shipment ordersare based on pickup and delivery in an on-demand manner ratherthan conventional scheduled routines. In this situation, it is nec-essary to estimate and compare the cost of shipments in order todetermine the cheapest one for a certain order. For now, these cal-culations are based on static, empirical estimates and simplifications,and do not reflect the complexity of the real world. In this thesis,we study the Maritime Pickup and Delivery Problem with Cost andTime Window Constraints. We first formulate the problem mathe-matically, which is conjectured NP-hard. Thereafter, we propose anA* based prototype which finds the optimal solution with complexityO(b d). We compare the prototype with a dynamic programming ap-proach and simulation results show that both algorithms find globaloptimal and that A* finds the solution more efficiently, traversingfewer nodes and edges.iii