Research On Supply-demand Pairing And Split Pickup And Delivery Vehicle Routing Problem

This dissertation studies a supply-demand pairing and split pickup and delivery vehicle routing problem.In this problem,the pairing of supply and demand among customers is unknown beforehand;split pickup and split delivery for a customer are allowed by multiple visits to the customer by the same or different vehicle(s);the solution consists of the supply-demand pairing decision and the vehicle routing decision.The problem is a complicated variant of classic vehicle routing problem;generally arises in the international crude oil transportation network,raw materials transferring network in the tobacco industry,the product rebalancing network in the fashion retailing chains and the bike re-balancing network in the sharing system.Based on this problem is high complex and has received much less attention,this paper deeply explores the problem from the perspective of mathematic model,heuristic algorithm and exact algorithm respectively.The main research results of the paper are discussed below:(1)The problem investigated in this paper consists of two interacted decisions.One is the pairing of supply and demand and the other is the vehicle routing.A mixed integer linear programming model is developed first as a basic model.Then,a novel unified model is proposed for simplification,by decoupling the interactions between the two decisions.Furthermore,a series of polynomial valid inequalities are proposed to strengthen the model.The experimental results show that the unified mode is easier to solve than the basic model and valid inequalities significantly improve the performance of the unified model.Lastly,we validate the effectiveness of the proposed model and inequalities for the closely related problem in the literature.(2)To address the larger size problem that often arises in real practice,based on the proposed unified model,we first design a greedy algorithm to obtain initial solutions quickly.Then,based on the idea of optimizing the decisions of the supply and demand pairing and vehicle routing,we develop seven efficient neighborhood structures.Next,a tabu search algorithm is proposed to improve the initial solution quality.In order to validate the performance of the algorithm,the lower bound of the problem is derived with CPLEX.The experimental results show that the search algorithm can provide high quality solutions for the problem investigated in this paper in a short time.Lastly,we validate the good-performance and marked superiority of the proposed heuristic algorithm on solving the closely related in the literature.(3)Based on the above unified model and polynomial valid inequalities,we first propose six classes of exponential valid inequalities.Then,we design the corresponding separation algorithm for each class of valid inequalities.Next,a branch-and-cut algorithm is proposed based on the discussion of the initial upper bound,preprocessing steps,branch strategies and implementation strategies for separation algorithm implementation.Computational experiments show that the proposed approach can solve the instance with up to 9 customers and 5 products,which are large problems compared to the solved instances in the related literature.Lastly,we validate the good-performance and superiority of the proposed exact algorithm on solving the closely related problem in the literature.