On Open Vehicle Routing Problem With Soft Time Windows And Its Applications

Vehicle routing problem (VRP) is the core of transport organizing optimization. In this dissertation, the characteristics, classification and algorithms of the VRP will be reviewed first of all.The Open Vehicle Routing Problem with Soft Time Windows (OVRPSTW) is widespread in practice. OVRPSTW is different to the basic vehicle routing problem (VRP). One difference is that OVRPSTW doesn't require the vehicle to return to the original starting depot after its completing the task, or if it requires the vehicle to return to the original starting depot, then a back trip along the original route is needed. Another difference is that OVRPSTW demands the service of the vehicle being in the customer's desired time windows, and if the service of the vehicle violates the customer's time windows, a penalty must be paid. In this dissertation, OVRPSTW will be studied theoretically. Based on the design of seven kinds of neighborhood structures and the introduction of a randomly diverse search process, a tabu search algorithm is constructed to solve OVRPSTW whose features are exploited. Starting with an initial solution which is generated randomly, the tabu search algorithm is tested with 56 benchmark problems. A comparison with other related approach in the literature is carried out. By the comparison, it shows that the proposed tabu search algorithm is good.Based on the theoretical study, the urban local post transportation network running data of Changsha City Post and the proposed tabu search algorithm are used to test two kinds of post routing, i.e., radial shape post routing and ring shape post routing which have four post routing programs. By comparing the result of every program with each other, the metaheuristic algorithm is visibly advantageous to the traditional planning manually in scheduling, and the radial shape post routing is much more better than the ring shape post routing in a medium-large-sized city which is with well-developed logistics business, a lot of business point, a wider distribution region, and a long vehicle running distance.The Multiple-Depot VRP (MDVRP) widely presents in many businesses. The research on MDVRP not only has practical value, but also is a base on supply-chain integration and coordination. To solve a Multi-Depot OVRPSTW (MDOVRPSTW) is more sophisticated. In this dissertation, the solution shows as arrange-customer-directly, a depot is selected randomly from the set of depots, and a vehicle in the selected depot is selected randomly to deliver to deal with the multiple depots. After completing final distribution in its routing, the selected vehicle goes to the nearest depot from it. Do so cyclically till all of the deliveries are completed. Thus, the MDOVRPSTW is solved integrally.With analyzing the beginning of agricultural products logistics, i.e., the transport logistics of agricultural products pickup, a research about the same and identified last customer of all vehicles which is claasified into a kind of an OVRPSTW named incomplete OVRPSTW (IOVRPSTW) is carried on. Meanwhile, a genetic algorithm is proposed to solve it. With simulating the agricultural products pickup logistics transport routing problem operated by a rural freight company who engages in third-party logistics business, an example of the agricultural products pickup logistics transport routing problem is constructed. The example is tested, and a satisfactorily optimal result is obtained, therefore, the genetic algorithm is indicated to be advantageous.