A Lagrangian Relaxation-based Heuristic for the Vehicle Routing Problems with Private Fleet and Common Carrier
|關鍵字:||車輛路線問題;委外運輸;集合涵蓋;拉氏鬆弛法;vehicle routing problem;common carrier;set covering;Lagrangian relaxation|
The delivery of goods from a warehouse to local customers is an important and practical decision problem of a logistics operator. In reality, we are facing the fluctuation of demand. When the total demand is greater than the whole capacity of the private fleet, we need to consider using the common carrier. In this study, we focus on the vehicle routing problem with private fleet and common carrier (VRPPC), in which a customer can be served by the private fleet or assigned to a common carrier. In order to balance computational load and solution quality and to address the issue of flexibility and simplicity, this study developed a heuristic algorithm based on several classical mathematical programming techniques. The VRPPC is first formulated in the form of the set covering problem (SCP), and the Lagrangian relaxation is used as the backbone in designing the iterative algorithm. In addition, a concept similar to column generation is used to update the solution space, a partial set of routes, to reduce computational load. The heuristic procedure was designed to find the feasible solution. Based on the numerical experiment, the solution quality of the heuristic algorithm is stable. The result suggests that the solution algorithm should be able to deal with the operational problems arising from a highly dynamic environment.
|Appears in Collections:||Thesis|
Files in This Item: