Research On The Vehicle Routing Problem With Pickups And Deliveries Under Handling Policies

Transportation plays a very important role in the modern logistics industry. The costof transportation operations occupies more50percent of the total costs of logisticsindustry according to the statistics of national statistical department. Therefore, if wecan enhance the effectiveness of transportation operations to reduce their cost, thewhole costs of logistics industry will decrease dramatically. Transportation can bedivided into two parts according to the distance: large-scale trunk line transportation andshort-distance city distribution. The vehicle routing problem is one of the mostsignificant issues in the short-distance city distribution. Many logistics companies try toreduce the transportation cost and improve the delivery service by optimizing the routeof vehicle.The vehicle routing problem with pickups and deliveries (VRPPD) is a vital versionof vehicle routing problem, it can serve the customers of pickups and deliveriessimultaneously to make the distributionoperations more effective and reduce moretransportation costs for the enterprises. The VRPPD under handling policies takes theloading and unloading of goods into account during the period of the optimization ofvehicle routing, and pursues to minimize the total costs includingvehicle routing costand rearrangement cost.Based on the literature, we propose a new handling strategy for the VRPPD, whichcan place the pickups at the front, middle, and rear of the vehicle, and execute fourjudgment steps: the placement of pickups at the rear of the vehicle directly, bigrearrangementbetween pickups and deliveries, smallrearrangement between pickups anddeliveries, and no exchange between pickups and deliveries. We give an example toprove that the new handling policy can reduce more handling costs than the other threepresented in literature. This combinatorial problem is then extended deeply at fourdirections below:Firstly, we just focus on the single vehicle for the VRPPD under handling policiesinchapter2: We formulate new models for the new handling policy, and analyze theexperiment. In chapter3-5, we then extend the single vehicle problem to the multiplevehicleone by inserting the capacity constraint, where four different models for thedifferent handling strategies are built again, and the solutions of the VRPPD areobtained.Secondly, we concern the size of the VRPPD under handling policies in chapter2and3: The combined problem forminiature cases is studied, in which therelationshipbetween the number of customers and the amount of the pickups and deliveries isdiscussed. Then the problem with large-scale instances is researchedcarefullyin chapter4and5, where the connection between the number of customers andthe computing times of the algorithmis analyzed.Thirdly, we pay attention to the different algorithms for the integrated problem.Initially, we make use of an exact method called branch and cut to solve the small-sizeproblemin chapter2and3, constructing the upper and lower bound and validinqualitiesbased on the integrated problem, and designing the pseudocode for thealgorithm. Subsequently, in chapter4and5, we solve the problem by applying ameta-heuristics named honey bees mating optimization, which includes constructing theinitial solutions, calculating the fitness function, mating, and optimizing the solutions byworker bees.Lastly, we concentrate on the different types of instances. Two types of academicinstances downloadedfrom the professional websites for the VRPPD are employed inthe second, third,and fourth chapters, and one type of real-world data coming from alogistics company is used to prove the validity of honey bees mating optimization in thefifth chapter.