کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475396 | 699301 | 2008 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Undirected postman problems with zigzagging option: A cutting-plane approach Undirected postman problems with zigzagging option: A cutting-plane approach](/preview/png/475396.png)
The paper devises a new model and associated cutting-plane and branch-and-cut approaches for a variant of the undirected Chinese and rural postman problem where some of the edges offer the flexibility of either being serviced twice by two separate traversals or by a single zigzag traversal. The kernel of the proposed cutting-plane algorithm is a separation procedure for generalized blossom inequalities. We show that the currently best known separation procedure of Letchford, Reinelt and Theis [A faster exact separation algorithm for blossom inequalities. In: Nemhauser G, Bienstock D, editors, Integer programming and combinatorial optimization, vol. 3064. Berlin: Springer; 2004. (chapter 10)] is applicable and leads to a highly efficient solution approach which can handle large-scale problem instances.
Journal: Computers & Operations Research - Volume 35, Issue 12, December 2008, Pages 3998–4009