The Ship Routing Problem: Formulation And Algorithms Based On VRPs

With the acceleration of the incorporation process of global logistics and the ship macro-scale developing trend, feeder-line networks must develop largely now and in the future. In the feeder-line shipping operations, Ship Routing Problems has played an important part in the profit of shipping company, and is the crucial factor of saving logistics cost of the society. However, until now, this kind .of work is decided by the experience and personal judgment of administrators. When the number of feeder ports mounts up, the exited formulation and algorithm would show their limitations.Based on the study of classical VRPs and the practical instances of Feeder-liner Shipping Rouging Problem, the dissertation proposes a new Mixed Integer Programming model, which is different from VRPs. The FSRP is different from the VRP with backhauls. However, the VRPB is traditionally assumed that on each route all deliveries have to be made before any cargo can be picked up to avoid rearranging the loads on the vehicle. Such a limitation can be relaxed for the FSRP. The FSRP is also different from the VRP with pickup and delivery (VRPPD). Both the coupling and precedence constraints, for the VRPPD, between the pickup and delivery stops can be relaxed for the FSRP, since its pickup cargoes in all feeder ports must be taken back to the hub. The difference between the FSRP and the VRPTW is that, for the FSPR, the hub port also has time window constraint besides all the feeder ports.The FSRP belongs to NP-hard problems. The dissertation develops a new immune genetic algorithm. Numerical experiments indicate the proposed methods are more effective in reducing the total shipping cost, compared to other famous algorithms.