Research Of Vehicle Routing Problem With Nodes Having Double Demands

In the classic vehicle routing problem (VRP), only the commodity’s delivery isconcerned about without the waste material’s recycling. But as the awareness ofenvironmental protection is enhanced and the waste goods’ usage can bring aboutadditional economic benefit, the reverse logistics is paid attention to more and more inthe recent years. In the environment where the reverse logistics exists, there is one casethat the customer ont only need the vehicle to distribute commdities to it but also needthe vehicle to collect the waste or the reusable materials from it, which leads to thevehicle should deliver goods according to the customers’ demand and bring away theuseless goods at the customer while serving it. When the served objects are somecustomers with double demands as above, the corresponding vehicle routing problemis called “the vehicle routing problem with nodes having double demands” abbreviatedas VRPNDD.Because VRP is NP-hard and VRP is the special case of VRPNDD when either ofthe demands is equal to zero, VRPNDD is NP-hard also in general conditions. In VRP,when the problem’s size is large, that is to say, the number of customers is greater than100, it is has already been very difficult to solve the problem for most of exactalgorithms. Most ot the actual problems in the real world are large-size problems, sothe heuristics is always focused by the people. To solve VRPNDD in the real worldneed to depend on the heuristics generally speaking, but under some special cases,does VRPNDD have polynomial algorithm? If it does, it is not necessary to design theheuristics. So the research about VRPNDD should contain the problem’s complexityunder the special case. The important attribute of the delivery and pickup doubledemands make VRPNDD has some new constructive properties and it is more complexto solve compared to VRP in which the customer has only delivery demand. So someresearches about the basic properties of VRPNDD should be done and the heuristicsbased on these properties should be designed. The main work and results in this paperare:(1) Researches about the computational complexity under the case that the vehicle’scapacity is equal to1and greater than or equal to2are done. The results show thatwhen the vehicle’s capacity is equal to1, and the distances are symmetric and satisfy the triangle inequality, VRPNDD has polynomial algorithm, but when thecapacity is greater than or equal to2, VRPNDD is NP-hard even if the distance issymmetric and satisfies the sharpened inequality.(2) Researches about the reducibility under the case that the vehicle’s capacity is equalto1and greater than or equal to2are done. The results show that when thevehicle’s capacity is equal to1and the distances are symmetric and satisfy thetriangle inequality, VRPNDD is reducible, but when the capacity is greater than orequal to2and the distances are symmetric and satisfy the triangle inequality,VRPNDD is unreducible.(3) Based on the characteristics of the solutions for the vehicle routing problem withsplit deliveries and pickups (SVRPPD), two constructive heuristics: the farthestnode split load algorithm (FNSL) without the limitation of used vehicles’ numberand the competitive decision algorithm (CDA) permitting the used vehicles’number unlimited are designed. The computing experiments show that FNSL hasbetter performance on the optimization of total travel distance compared with theexisted algorithms, i.e. the farthest node full split algorithm (FNFL) and the nearestnode full split algorithm (NNFL), but the used vehicles number is more than theother two algorithms’, which shows that FNSL is applicable to the environmentwhere the time is restricted strictly. CDA’s solutions can guarantee the traveldistances is the shortest under the condition that the used vehicles number is theleast. Then CDA is used to test the benchmark of SVRPPD, and some comparisonsare done with the existed heuristics and the solutions show that CDA has excellentperformance.(4) Researches about the vehicle routing problem with split deliveries and pickups andtime windows (SVRPPDTW) are done. Greedy algorithm (GA), two stagealgorithm (TS) and CDA are designed to solve SVRPPDTW. Based on thebenchmark of the vehicle routing problem with time windows (VRPTW), somenew instances adapted to VRPNDD with time windows are generated. Theproposed algorithms are tested on the new instances and the CPLEX optimizationsoftware are used to solve the lower bound model. The results show that GA andTS performance well under the condition that the problem’s size is small, butCDA’s superiority increases as the problem size’s increasing, but the gap with thelower bound increases too. (5) An overview about the vehicle routing problem with simultaneous deliveries andpickups (VRPSDP) are given. The research results of the overview show that theparallel algorithms’ research and designment about the metaheuristics withparallelism in it are not enough and the improvement for the serial algorithmsshould be done in two aspects, i.e. searching for better initial solutions andsearching for valid hybrid algorithms.(6) CDA algorithms of VRPSDP are designed. The comparisons among the testedresults of the existed constructive heuristics and CDA on the VRPSDP benchmarkshow that CDA performs well under the condition that the customers locations areclustered.