| Grain is the country's important economic and strategic materials. The provisionstransportation problem is an important issue for the state's grain management departments and grain enterprises needing to be urgently resolved. With the Electronic Commerce and the third-party logistics appearing, there has founded specialized logistics enterprises for the provisions transportation, and created a new model for the professionalism grain logistics and cost savings. For the provisions transportation problem, theruntime, cost, and risk, etc. should be taken into account. Compared with the generaltransportation, the provisions transportation problem becomes a multi-objective problem. Furthermore, the time will affect the cost, risk etc. in the transportation. To studythe time-varying provisions transportation problem has a strong society background andextensive application perspective.In the present literature, the time-varying logistics was usually based on the urbantraffic. The urban traffic takes one day as a period. The provisions transportation is different from the urban traffic, because it is an interregional transportation. It needs severalperiods to complete the transport process. Therefore, by considering the characteristicsof provisions transportation, it is necessary to study the periodic time-varying logisticsscheduling problem. This paper starts from the special time-varying network with theshortest path problem and then sets up models and algorithms. The main research results are as follows: First of all, we establish the shortest time path model with periodic-time-varying. We use integer modular arithmetic to get the state transform equation. Weassume a period is partitioned into K parts, k = 0,1,…, K-1. Let t(i, j, k) be the transit time needed to traversed from the vertex i to the vertex j, and the departure time atthe vertex i is k. Then the time when we arrive the vertex j is k' = [k + t(i, j, A;)] (mod K).By introducing two decision variables: x(i,j,k) and y(i,k), we get the the shortest time path model:Here (0.0.7) means that we want to find the shortest time path. (0.0.8) means that thedeparture time at the vertex s is 0. (0.0.9) means that we can arrive the vertex d at anytime. (0.0.10) means the vertex that the vehicle passes by. (0.0.11) is the state transformequation. (0.0.12) is the (0,1) variable. This is a (0,1) linear programming.Since it is very hard to solve the (0,1) linear programming, we should put it into agraph model. We put the vertex in different time into different verteices, and connectverteices according to the state transform equation. Then we get the extendable networkG. If we assume K is a constant, we can use the known shortest path algorithm to solveit.Based on the one objective problem, we study the periodic time-varying provisionstransportation problem with bi-objective functions which include time and cost. There areseveral methods to be discussed. The first two models are polynomial solvable. Becausethe last model is NP-hard, we discuss the heuristic algorithm to find effective path set.In the conclusion, we point out the main innovation of the paper and the perspectivefor the further research. |
