Chinese postman problem with priority nodes

• Autorzy: Kramberger T. , Štrubelj G. , Žerovnik J.
• Języki publikacji: EN

Abstrakty

EN

A generalization of the Chinese Postman Problem is studied in which the delays at a subset of priority nodes are penalized in the cost function. As it is shown that the problem is NP-hard, two tour constructing heuristics are proposed, and their properties are studied. It is proved that one of the heuristics gives optimal solutions on a subset of instances with bounded cost of delays. The implementations of the heuristics are compared on several types of randomly generated instances.

Słowa kluczowe

EN

Chinese postman problem; ARP(Arc Routing Problems); heuristics; Eulerian graph

PL

problem chińskiego listonosza; neurystyka; wykres Eulera

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2009
• Tom: Vol. 34, No. 4
• Strony: 233--264
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Kramberger T.

autor

Štrubelj G.

autor

Žerovnik J.

• University of Maribor, Faculty of Logistics, Cejle, Slovenia,

Bibliografia

• [1] Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M., The Minimum Latency Problem, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, Montreal, Quebec, Canada, 1994, 163-171.
• [2] Brest, J., Žerovnik, J., An approximation algorithm for the asymmetric traveling salesman problem, Ricerca operativa 28, 1999, 59-67.
• [3] Brightwell, G. R., Winkler, P., Note on Counting Eulerian Circuits, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, Montreal, 1991, 175-181.
• [4] Chabrier, A., Vehicle Routing Problem with elementary shortest path based column generation, Computers & Operations Research 33, 2006, 2972-2990.
• [5] Dijkstra, E. W., A note on two problems in connection with graphs, Numerische Mathematik 1, 1959, 269-271.
• [6] Dror, M. , Stern, H., Trudeau, P., Postman Tour on a Graph with Precedence Relation On Arcs, Networks 17, 1987, 283-294.
• [7] Edmonds, J., The Chinese Postman's Problem, ORSA Bull. 13, 1965, 283-294
• [8] Eiselt, H. A., Gendreau, M., Laporte, G., Arc routing problems, Part I: The Chinese postman problem, Operations Research 43(2), 1995, 231-242.
• [9] Eiselt, H. A., Gendreau, M., Laporte, G., Arc routing problem, Part II: The Rural postman problem, Operations Research 43(3), 1995, 399-414.
• [10] Fleischner, H., Eulerian graphs and related topics, Part 1, vol 2, Annals of discrete mathematics 50, Elsevier Science Publishers, Amsterdam, 1991.
• [11] Fleury, Deux problemes de geometrie de situation, Journal de mathematiques elementaires, 1883, 257-261.
• [12] Guan, M., Graphic Programming using odd and even points, Chinese Mathematics 1, 1962, 273-277.
• [13] Korte, B., Vygen J., Combinatorial optimization: Theory and algorithms, Springer, Berlin, Heidelberg, New York, 2002.
• [14] Kramberger, T., Žerovnik J., Chinese Postman Problem With Priorities, Proceedings SOR'05, Nova Gorica, Slovenia, 2005, 357-362.
• [15] Kramberger, T., Žerovnik J., A contribution to environmentally friendly winter road maintenance: Optimizing road de-icing, Transportation Research Part D 13, 2008, 340-346.
• [16] Kruskal, J. B., On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proceedings of the American Mathematical Society, 7(1), 1956, 48-50.
• [17] Lemieux, P. F., Campagna, L., The snow ploughing problem solved by a graph theory algorithm, Civil Engineering Systems 1, 1984, 337-341.
• [18] Letchford, A. N., Eglese, R. W., The Rural Postman Problem with Deadline Classes, European Journal of Operational Research 105, 1998, 390-400.
• [19] Mehlhorn, K., Näher, S., LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, Cambridge, 1999.
• [20] Ngueve, S. U., Prins, C., Wolfler-Calvo,. R., A Memetic Algorithm for the Cumulative Capacitated Vehicle Routing Problem, EU/MEeting 2008 - Troyes, Prance, 2008.
• [21] Pesek, I., Schaerf, A., Žerovnik, J., Hybrid Local Search Techniques for the Resource-Constrained Project Scheduling Problem, Lecture Notes in Computer Science 4771, 2007,57-68.
• [22] Pevzner, P. A., Tang, H., Waterman, M. S., An Eulerian path approach to DNA fragment assembly, Proceedings oft he National Academy of Sciences, 98(17), 2001, 9748-9753.
• [23] Shao, J., Lister, P.J., Data filtering of thermal mapping of road surface temperatures, Meteorological Application 2, 1995, 131-135.
• [24] Shao, J., Lister P.J., Hart G.D., Pearson H.B., Thermal mapping: reliability and repeatability, Meteorological Applications 1997, 131-137.
• [25] Skiena, S., Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, Redwood City, CA, 1990.
• [26] Thimbleby, H., The directed Chinese Postman Problem, Software Practice & Exp., 33(11), 2003, 1081-1096.
• [27] Thimbleby, H.W., Witten, I. H., User Modelling as Machine Identification: New Methods for HCI, Advances in Human-Computer Interaction, H. R. Harts on & D. Hix, eds., IV, 1993, 58-86.
• [28] Thornes, J.E., Thermal Mapping and road- weather information systems for highway engineers, In Highway Meteorology, ed. By A. H. Perry and L. J. Symons, 1991,39-67.