Linear Programming of the Loopwise Route Representation for the Shortest Path Problems by Introducing the Reference Link Flow

Abstract

Loopwise route representation (LRR), which has been recently proposed as an alternative network representation, can determine the optimal path for the vehicle routing problems with a simpler optimization formulation. However, it requires a significant computing burden due to nonlinear optimization. This study proposes a novel linearization approach for the LRR by introducing the reference link flow. The proposed method consists of two stages: selecting the reference link flow in Stage 1 and formulating a linearized optimization problem in Stage 2. Through the above two stages, the proposed method does not require nonlinear functions while maintaining the unique advantages of the LRR. To validate the performance of the proposed method, numerical experiments are designed with ideal grid-type networks of various sizes. For comparison, integer linear programming (ILP) is conducted in the corresponding link-wise route representation. Numerical results demonstrate that the proposed linearization outperforms conventional ILP in terms of computing time and solution accuracy. For a $100\times 100$ grid-type network, the proposed method takes 0.15 seconds, whereas conventional ILP takes 1.39 seconds. Furthermore, the proposed method provides a 0-to-1% relative error (i.e., optimal and near-optimal solutions) in 802 cases out of total 1000 cases, whereas conventional ILP provides the same level of errors only in 406 cases. With further work, the proposed linearization scheme could be applied to other vehicle routing problems such as a traveling salesman problem in order to enhance a computational efficiency.

Keywords

• Loop-wise route representation
• linear programming
• reference link flow
• shortest path problem
• topology optimization
• vehicle routing problem