Research On The Model And Algorithm For Chemical Ship Routing And Scheduling Problem

The maritime transport of bulk chemicals is an important part in the global supply chain.As a typical capital-intensive industry,the chemical carriers must make effective strategies to increase revenue and reduce expenditure when facing high shipping costs.In the tramp service,there are dozens or hundreds of market orders,involving ports all over the world.How to select the order for the fleet can bring the best benefits,and how to plan the route to minimize the transportation cost is a difficult problem faced by the major chemical carriers.Compared with enterprises making decision manually at present,the operation optimization method can help to make decisions faster and better,and improve their market competitiveness.The chemical tankers routing and scheduling problem studied in this paper aims to develop an operational plan for a fleet of multi-parcel chemical tankers with different ship types.Ship capacity,operating cost and initial state are different,which may be waiting at a port or on its way to a port.Each order includes pickup port,unloading port,quantity and profit.In consideration of the pickup time window constrains and the restriction of incompatible between ship and cargo,and between cargo and cargo,the carriers seek to choose the cargos to transport and determine the optimal route that the ship should follow to maximize its profit.This problem is a new complex largescale combinatorial optimization problem.At present,there are few researches on the maritime transport scheduling of chemicals in China,and even fewer studies considering the characteristics of ship-to-cargo and cargo-to-cargo incompatibility.In this paper,the model of the problem is established and a variety of algorithms are used to solve it.The main research results are as follows:(1)This paper introduces the basic process of chemical maritime transportation、Structure of chemical maritime transportation network and the feature of chemical ship and cargo transportation.This paper summarizes and introduces a variety of scheduling decision-making problems involved in the chemical maritime transportation business,and analyzes the relevant research from different emphases and perspectives.(2)According to the chemical shipping scheduling problem based on order selection studied in this paper,the key characteristics of the problem are analyzed,such as multiple ship types,time window constraints,incompatibility constraints,pickup and delivery constraints and so on.Based on the linear programming theory,the MILP model of this problem is established.At the same time,considering that there are many time constraints and strong logical relationship between the objects,the constraint programming model of the problem is proposed by using constraint programming(CP)method based on artificial intelligence.The model is solved by ILOG CPLEX and ILOG CP solver respectively.However,due to the complexity of the problem,the solver can not directly solve the practical application scale.(3)Considering that the problem studied in this paper is a complex combinatorial optimization problem,it is difficult to find the optimal solution by the exact algorithm and the constraint programming algorithm based on global search.Therefore,particle swarm optimization(PSO)algorithm is developed.The performance of exact algorithm,constraint programming algorithm and particle swarm optimization algorithm are tested by experiments.The results show that the MILP model and CP model can effectively obtain the optimal solution for the small-scale problem,and PSO can solve the large-scale problems,however,in small-scale problems,it is more capable of searching feasible solutions.(4)To optimize the algorithm,an algorithm optimization idea based on heuristic iterative rules is proposed.The iterative design of the exact algorithm based on MILP and the particle swarm optimization algorithm is implemented respectively.The performance of the two algorithms is analyzed and compared through experiments.Through large-scale numerical experiments,the efficiency of the exact algorithm in solving the single ship problem makes the iterative algorithm based on MILP better.