-
- Roberto Baldacci
- Department of Electronics, Computer Science and Systems, University of Bologna, 47521 Cesena, Italy
-
- Aristide Mingozzi
- Department of Mathematics, University of Bologna, 47521 Cesena, Italy
-
- Roberto Roberti
- DEIS, University of Bologna, 40136 Bologna, Italy
書誌事項
- 公開日
- 2011-10
- DOI
-
- 10.1287/opre.1110.0975
- 公開者
- Institute for Operations Research and the Management Sciences (INFORMS)
この論文をさがす
説明
<jats:p> In this paper, we describe an effective exact method for solving both the capacitated vehicle routing problem (cvrp) and the vehicle routing problem with time windows (vrptw) that improves the method proposed by Baldacci et al. [Baldacci, R., N. Christofides, A. Mingozzi. 2008. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2) 351–385] for the cvrp. The proposed algorithm is based on the set partitioning (SP) formulation of the problem. We introduce a new route relaxation called ng-route, used by different dual ascent heuristics to find near-optimal dual solutions of the LP-relaxation of the SP model. We describe a column-and-cut generation algorithm strengthened by valid inequalities that uses a new strategy for solving the pricing problem. The new ng-route relaxation and the different dual solutions achieved allow us to generate a reduced SP problem containing all routes of any optimal solution that is finally solved by an integer programming solver. The proposed method solves four of the five open Solomon's vrptw instances and significantly improves the running times of state-of-the-art algorithms for both vrptw and cvrp. </jats:p>
収録刊行物
-
- Operations Research
-
Operations Research 59 (5), 1269-1283, 2011-10
Institute for Operations Research and the Management Sciences (INFORMS)