Research On The Optimization Of Near-sea Container Liner Shipping With Time Windows

With the in-depth promotion of China’s "One Belt One Road" initiative and the Regional Comprehensive Economic Partnership,the process of regional integration in Asia has been accelerated rapidly.As a result,the demand for shipping within the region has maintained rapid growth.However,due to the reduction in entry threshold of near-ocean routes,more and more liner companies increase their lauched capacity in this region.The situation of overcapacity is still a growing severe problem.In order to survive from the fierce market competition at regional level,how to reduce operating costs through scientific and reasonable scheduling,speed control and optimization of route layout has become an urgent problem for the near-sea container lines to be solved.After systematically summarizing and analyzing the literature on the schedule design,speed optimization and route design for liner transportation,it is found that few researches have involved the time window.In practice,the influence of the time window of liner transportation on the schedule arrangement,speed control and route adjustment of container liner is significant.To fullfil this gap,this paper considers the characteristics of near-sea container liner transportation and conducts the following researches:First,the problem of ship schedule design and speed optimization of near-sea container liner routes with port time windows are studied.For a given liner shipping route,considering the special in port characteristics of near-sea routes i.e.the short lay time and the periodic nature of the time windows,a mixed integer nonlinear programming model is developed with the objective of minimizing the total weekly operating cost of the route.In addition,to transform the nonlinear model to an equivalent linear model,the nonlinear constrain of in port time windows is transformed into a linear constrain without infeasible solution by using integar programming method.Second,the problem of ship schedule design and speed optimization of near-sea container liner routes considering freight demands’ time windows are studied.Considering the influence of freight demands’ time window and container OD shipping time on ship schedule and sailing speed,the ship schedule and sailing speed are optimized for a given liner shipping route by converting the customer’s time preference on ship arrival time into a soft time window constraint.A penalty or bonus is generated by using the difference between the actual container OD shipping time and the marketlevel shipping time.Then,a mixed integer nonlinear programming model is established to minimize the total weekly operating cost of the route.Meanwhile,the piecewise functions in the model is linearized and the power function in the objective function is approximated by using an outer approximation algorithm with a predetermined optimality tolerance level ε.Finally,a mixed integer linear programming model is obtained.Third,on the basis of the previous study,the optimization of port call sequence of the circular route is incorporated into the modeling.A modeling method combining route design and speed optimization with port time window is proposed to establish a mixed integer nonlinear programming model to minimize the total weekly operating cost of the route.Meanwhile,a joint optimization of the port call sequence,speed on each shipping leg,ship arrival time,number of ships deployed on the route,and shipping path of each container OD demand is performed.The penalty function method is used to convert the port time window constraint into a piecewise function,which is added to the objective function and linearized.And the power function in the objective function is approximated by an outer approximation algorithm with a predetermined relative error ε.Then,the model is approximately transformed in a mixed integer linear programming model.Finally,on the basis of the above study,the model is extended to pendulum routes and complex routes.The situation that each port can be visited twice in a round-trip journey and the same shipping leg can exist in both the head-haul and back-haul directions is implemented in the modeling.Then,a mixed integer nonlinear programming model is established to minimize the total weekly operating cost of the route.The nonlinear model is approximately transformed into a mixed integer linear programming model by using integer programming techniques,penalty function method and relative error-based optimal outer approximation algorithm.At last,a series of numerical experiments are conducted to verify the efficiency of the model and algorithm for each of the above four problems.Results show that in shipping schedule design and speed optimization problems,both port time window and freight demand time window affect the total operating cost,sailing speeds and ship arrival times.In addition,owing to the short length of a roundtrip in near-sea routes,when container lines face changes in various factors,there is little room to adjust the number of ships deployed on the designed service route.In the problem of ship route design and speed optimization of the circular route with port time windows,a higher fuel price or a lower port efficiency leads to higher total cost,but their changes hardly cause the changes in the optimal port call sequence of wrap-around routes;with the relaxation of port time windows,a better port call sequence could be available to reduce the total operating cost.In the problem of ship route design and speed optimization of the pendulum route with port time windows,the optimal port call sequence may change with the increase of fuel price;with the relaxation of the port time windows,there may be a better port call sequence to effectively reduce the total operating cost;when the port handling efficiency decreases,the total operating cost of the pendulum route can be effectively reduced by increasing the number of ships on the route;when the container demand decreases,the total operating cost of the pendulum route can be effectively reduced by skipping certain ports.