Preview

Труды Института системного программирования РАН

Расширенный поиск

Варианты задач китайского почтальона и их решения через преобразование в задачи маршрутизации

https://doi.org/10.15514/ISPRAS-2018-30(3)-16

Полный текст:

Аннотация

В статье описаны проблемы маршрутизации. Показано, что почти все проблемы маршрутизации дуг могут быть преобразованы в другие проблемы маршрутизации. Это продемонстрировано на примере задачи китайского почтальона в смешанном мультиграфе. Также в статье приведен обзор различных задач китайского почтальона (в зависимости от типа графа, функции стоимости и обязательности прохождения элементов графа). Для каждой проблемы дана математическая постановка. Кроме того, описаны примеры потенциально полезных приложений, где задачи могут быть применены. Приведена таблица различных вариантов задачи китайского почтальона и выбраны параметры для идентификации различных типов задач. Выделено пять параметров: наличие дуг, наличие ребер, наличие обязательных дуг, наличие обязательных ребер, наличие ребер со стоимостью, зависящей от прохода. Показано, что, варьируя эти параметры, можно получить новые задачи, которые могут быть полезны в реальной жизни, однако еще не описаны. Выявлены четыре таких задачи. Показано, что задача китайского почтальона может быть решена путем преобразования в другие задачи маршрутизации. Приведен метод, позволяющий преобразовать задачу в обобщенную задачу коммивояжера. Показаны результаты применения простейших алгоритмов для решения преобразованного варианта задачи (результаты приведены для алгоритмов ближайшего соседа и их модификаций). Исследование еще не завершено, планируется продолжать тестировать алгоритмы решения смежных задач маршрутизации и алгоритмы для преобразований задач в эквивалентные.

Об авторах

М. К. Горденко
Департамент программной инженерии, Национальный исследовательский университет “Высшая школа экономики”
Россия


С. М. Авдошин
Департамент программной инженерии, Национальный исследовательский университет “Высшая школа экономики”
Россия


Список литературы

1. Eglese R., Letchford A., General Routing Problem. In Encyclopedia of Optimization. Springer, Boston, MA. 2008.

2. Thimbleby, H. The directed chinese postman problem. Software: Practice and Experience, 33(11), 2003, pp. 1081-1096.

3. Toth P., Vigo D. (ed.). The vehicle routing problem. – Society for Industrial and Applied Mathematics, 2002.

4. Hertz A., Laporte G., Mittaz M. A tabu search heuristic for the capacitated arc routing problem. Operations research, vol. 48, no. 1, 2000, pp. 129-135.

5. Zerbino D. R., Birney E. Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome research, vol. 18, no. 5, 2008, pp. 821-829.

6. Edmonds J., Johnson E. L. Matching, Euler tours and the Chinese postman. Mathematical programming, vol. 5, no. 1, 1973, pp. 88- 124.

7. Kolmogorov V. Blossom V: a new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, vol. 1, no. 1, 2009, pp. 43-67.

8. Robinson H. Graph theory techniques in model-based testing. In Proc. of the International Conference on Testing Computer Software, 1999.

9. Wilson R. J. An eulerian trail through Königsberg. Journal of graph theory, vol., 10, no. 3, 1986, pp. 265-275.

10. Ababei C., Kavasseri R. Efficient network reconfiguration using minimum cost maximum flow-based branch exchanges and random walks-based loss estimations, IEEE Transactions on Power Systems, vol. 26, no. 1, 2010, pp.. 30-37.

11. Chen W. H. Test sequence generation from the protocol data portion based on the Selecting Chinese Postman algorithm. Information Processing Letters, vol. 65, no. 5, pp. 261-268.

12. Aho A.V. et al. An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours. IEEE transactions on communications, vol. 39, no. 11, 1991, pp, 1604-1615.

13. Dror M. (ed.). Arc routing: theory, solutions and applications. Springer Science & Business Media, 2012.

14. Ghiani G., Improta G. An algorithm for the hierarchical Chinese postman problem. Operations Research Letters, vol. 26, no. 1, 2000, pp. 27- 32.

15. Longo H., De Aragão M. P., Uchoa E. Solving capacitated arc routing problems using a transformation to the CVRP. Computers & Operations Research, vol. 33, no. 6, pp. 1823-1837.

16. Pearn W. L., Assad A., Golden B. L. Transforming arc routing into node routing problems, Computers & operations research, vol. 14, no. 4, 1987, pp. 285-288.

17. Laporte G. Modeling and solving several classes of arc routing problems as traveling salesman problems. Computers & operations research, vol. 24, no. 11, 1997, pp. 1057-1061.

18. Fischetti M., Salazar González J. J., Toth P. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, vol. 45, no. 3. 1997. pp. 378-394.

19. Solomon M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations research, vol. 35, no. 2, 1987, pp. 254-265.

20. Modares A., Somhom S., Enkawa T. A self-organizing neural network approach for multiple traveling salesman and vehicle routing problems. International Transactions in Operational Research, vol. 6, no. 6, 1999, pp. 591-606.

21. Cheung K.L., Fu A.W.C. Enhanced nearest neighbor search on the R-tree. ACM SIGMOD Record, vol. 27, no. 3, 1998. pp. 16-21.

22. Tao Y., Papadias D., Shen Q. Continuous nearest neighbor search. In Proceedings of the 28th International Conference on Very Large Databases, 2002, pp. 287-298.

23. Pimentel F. G. S. L. Double-ended nearest and loneliest neighbour: a nearest neighbour heuristic variation for the travelling salesman problem. Revista de Ciências da Computação, vol. 6, issue 6, 2011.


Для цитирования:


Горденко М.К., Авдошин С.М. Варианты задач китайского почтальона и их решения через преобразование в задачи маршрутизации. Труды Института системного программирования РАН. 2018;30(3):221-232. https://doi.org/10.15514/ISPRAS-2018-30(3)-16

For citation:


Gordenko M.K., Avdoshin S.M. Variants of Chinese Postman Problems and a Way of Solving through Transformation into Vehicle Routing Problems. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(3):221-232. https://doi.org/10.15514/ISPRAS-2018-30(3)-16

Просмотров: 973


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)