The Research Of Tabu Search Algorithms For Allied Vehicle Routing Problem With Traffic Flow

With the development of social economy, logistic management and optimization are becoming more and more important. The high cost of transportation requires the research on transportation optimization methods and theories. Allied Vehicle Routing Problem(AVRP) is the exact way dealing with optimization of vehicle routing and scheduling based on logistic alliance. As a part of the National Natural Science Foundation-funded project "Reasearch of Allied Vehicle Routing Problem", the research on allied vehicle routing problem with traffic flow(AVRPTF ) is practical and is very important for arranging vehicle routings in real distribution works.The main achievement of this dissertation is that: The traffic flow constraints are introduced into AVRP for the first time.The models of AVRP with Static Traffic Flow(AVRPSTF), AVRP with Time-Dependent Traffic Flow(AVRPTDTF), AVRP with Traffic Flow in Normal Distribution(AVRPTFND) and AVRP with Non-Deterministic Traffic Flow(AVRPNDTF) are builded. And four types of tabu search algorithm are designed to solve the problems.The main work of this dissertation is as follows:1. AVRPSTF is on research. A multi-initial-solution and a global tabu list are used in the algorithm to strengthen the stability and enlarge the search scopes. Compared with the standard TS, the proposed TS algorithm has greatly improved its global search capacity. Then, an example is given to show the advantage of this experiment.2. AVRPTDTF is on research. The initial solution in our case is generated through a hybrid operation of the modified savings method of Clarke and Wright. In this TS algorithm, we have used a more powerful neighbourhood structure to increase its search ablility. Afterward, an example is given for test.3. AVRPTFND is on research. The idea for solving the problems is divided into two steps. A novel adaptive search strategy of intensification and diversification is proposed in this TS algorithm. This strategy dynamically adjusts the numbers of intensification elements and diversification elements in candidate list respectively by interactive cooperation between neighbourhood and candidate list. Experiment showed that this TS algorithm is feasible and effective.4. AVRPNDTF is on research. Aiming at dealing with the uncertainty of traffic flow, a local dynamic optimization strategy is proposed. Our TS algorithm to solve the AVRPNDTF is based on reactive tabu search(RTS ) with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way in order to get a balanced intensification and diversification continuously during the search process. Experiment showed that this TS algorithm is effective.