Research On Scheduling Optimization Problems In Less-than-truckload Logistics Based On Graph Coloring Model

The scheduling optimization problems in less-than-truckload logistics have always been deeply considered by many enterprises, which means assigning and using the current scheduling resources properly through the less-than-truckload logistics transportation, and then realizing to decrease the cost and achieve economies of scale. Generally, the research work for the scheduling optimization problems in less-than-truckload logistics is mainly about the decision procedure on the cargos, trucks and personnels, and the scheduling plan should be made according to the detail application environment and customer demands.During the procedure of decision making for the problems in less-than-truckload logistics, the most important part is solving the conflicts phenomenon of using the logistics resources according to the current objectives and constraints, in order to provide reliable operation environment for each participator in logistics activities. Meanwhile, there are many new features equiped by less-than-truckload logistics compared with truckload logistics, which makes the related decision problems more complicated, as a result of that, we need to describe and model the problem from some new perspectives. This paper introduces the research work about the bin packing, vehicle routing and driver scheduling problems based on the real demands in less-than-truckload logistics, and then describes and solves the three problems through graph coloring model in graph theory.The research work of this paper could be divided into three parts:(1) Modelling and solving the bin packing problem with conflicts(BPPC). The research work is about a kind of bin packing problem with conflict relationship constraints among some cargos according to the loading scheduling link in less-than-truckload logistics, and which contains five parts: Firstly, a demand analysis is finished about the loading business, and some assumptions are summarized about the packing operations in the actual environment. Secondly, according to the results of demand analysis, the mathematical planning model of BPPC is created, and then transformed into the vertex coloring model based on the discussion of complexity of BPPC. Thirdly, a two-stage heuristic algorithm for BPPC is designed and implemented based on the greedy coloring operations. Fourthly, another two-stage heuristic algorithm for BPPC is designed and implemented based on the maximum clique computing operations. Lastly, the effectiveness of the model and algorithm is verified by computing of the simulation experiments.(2) Modelling and solving the double traveling salesman problem with multiple stacks(DTSPMS). The research work is about a kind of vehicle routing problem with sequence constraints of loading and unloading operations according to the distribution scheduling link in less-than-truckload logistics, and which contains four parts: Firstly, a demand analysis is finished about the concentralized distribution business, and some assumptions are summarized about the routing operations in the actual environment. Secondly, according to the results of demand analysis, the mathematical planning model of DTSPMS is created, and then the determining procedure to the feasibility of a solution is transformed into the bounded graph coloring problem on a permutation graph structure. Thirdly, a tabu search is designed and implemented for solving DTSPMS. Lastly, the effectiveness of the model and tabu search algorithm is verified by computing of the simulation experiments.(3) Modelling and solving the driver scheduling problem with time delay disruption. The research work is about a kind of driver scheduling problem which is affected by the time delay disruption of transportation tasks, and contains four parts: Firstly, a demand analysis is finished about the driver scheduling business, and some disruption events related to the problem are summarized. Secondly, according to the results of demand analysis, the set of transportation tasks is represented by an interval graph structure, and the driver scheduling problem with time delay disruption is modelled by a robust graph coloring problem on the interval graph. Thirdly, a genetic algorithm is designed and implemented for solving the driver scheduling problem with time delay disruption. Lastly, the effectiveness of the model and genetic algorithm is verified by computing of the simulation experiments.