A Benders Decomposition Approach for the Multivehicle Production Routing Problem with Order-up-to-Level Policy
发布时间:12-08-21

Zhenzhen Zhang, Zhixing Luo, Roberto Baldacci, Andrew Lim

Transportation Science, 55(1), 160-178, 2021

Recommend Reason

The integrated supply chain usually involves several important decisions in the given planning horizon, such as production, inventory, distribution, and routing decisions. Due to the great computational complexity of the joint optimization, these decisions are usually decided in a sequential fashion. However, the generated solution is not globally optimal, and even infeasible in many cases. To overcome these issues, we proposed a logic-based Benders’ decomposition approach to jointly determine the involved decisions and improve its computational efficiency. The experiments demonstrate that the proposed approach is hundreds of times faster than inferior mathematical programming-based algorithms existed in the literature on many instances.

About the Authors

Zhenzhen Zhang, School of Economics and Management, Tongji University

Zhixing Luo, Nanjing University

Roberto Baldacci, University of Bologna, Italy

Andrew Lim, National University of Singapore

Keywords

production routing problem, logic Benders’ decomposition, set partitioning model

Brief Introduction

The production routing problem (PRP) arises in the applications of integrated supply chain which jointly optimize the production, inventory, distribution, and routing decisions. The literature on this problem is quite rare due to its complexity. In this paper, we consider the multivehicle PRP (MVPRP) with order-up-to-level inventory replenishment policy, where every time a customer is visited, the quantity delivered is such that the maximum inventory level is reached. We propose an exact Benders’ decomposition approach to solve the MVPRP, which decomposes the problem as a master problem and a slave problem. The master problem decides whether to produce the product, the quantity to be produced, and the customers to be replenished for every period of the planning horizon. The resulting slave problem decomposes into a capacitated vehicle routing problem for each period of the planning horizon where each problem is solved using an exact algorithm based on the set partitioning model, and the identified feasibility and optimality cuts are added to the master problem to guide the solution process. Valid inequalities and initial optimality cuts are used to strengthen the linear programming relaxation of the master formulation. The exact method is tested on MVPRP instances and on instances of the multivehicle vendor-managed inventory routing problem, a special case of the MVPRP, and the good performance of the proposed approach is demonstrated.

Link:https://pubsonline.informs.org/doi/abs/10.1287/trsc.2019.0964

 

关闭 微信扫一扫

X Thank you for your interest in Master of Global Management, Tongji University!