关于中国邮递员问题研究和发展的历史回顾

中国邮递员问题是运筹学研究的基本问题之一. 回顾了中国邮递员问题提出和解决的历史,同时,介绍了对此问题研究的发展概况.     

图论中若干著名问题的历史注记

考察了哥尼斯堡七桥问题,最小生成树问题,旅行推销员问题,分派问题,最大流问题,中国邮递员问题和四色问题等著名图论问题的历史背景.     

战争地区邮递员问题

本文首次提出了赋权有向图上中国邮递员问题的一个推广－战争地区邮递员问题，并对解的存在性给出了若干充分条件和必要条件，得到了求解该问题的一个多项式算法。     

水灾地区邮递员问题

本文首次提出了中国邮递员问题的推广问题－水灾地区邮递员问题,并对解的存在性给出了一系列的充分条件、必要条件及充要条件,得到了求解该问题的一个多项式算法。     

CARP中一个与Pearn下限等价的新算法

<正> 有约束边运行问题(CARP),包括有约束中国邮递员问题(CCPP)在内,是近年来颇受关注的一个运筹管理问题,该问题通常定义如下:     

带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

垄断服务系统公共损耗费用分摊理论基础分析

就具有最简单结构的抽象垄断服务系统的基本特性及其公共损耗的费用分摊问题建立了较为完整的公平性与合理性公理体系.同时,利用边际损耗原则导出了一类满足公理组的费用分摊方法,并将所得结论应用于电力系统有功网损费用分摊问题,从理论上统一了现有的几类主要的分摊方法.分析结论表明:损耗结构分析和费用分摊原则的确定在本质上从属于不同层次的问题.特别地,对不分明损耗而言:它们还是不可分割的统一体.对这一类问题进行描述必须考虑综合运用数学、社会学、经济学和方法论原则.     

约束最优路线问题的模拟退火解法

本以１９９８年全国大学生数模竞赛中的Ｂ题（即“灾情巡视路线”）为例,介绍一种最优路线问题的方法－－模拟退火法＾「１」。该法对旅行推销员、中国邮递员等问题,即使有约束条件,也能求得较好的近似解,具有适用范围广和可拓展的优点。     

考虑完整交易费用的组合证券投资求解

针对中国证券市场现存的各种交易费用,建立一个更加符合实际的组合证券投资模型.该模型不仅继承了股票不可拆分、不能卖空等特点,而且完全反映了交易费用的核算情况;最后给出一个遗传算法结合动态罚函数求解的投资实例,计算结果证明了该模型及其求解方法的有效性和可操作性.     

阿飞上班记

烧脑指数: 趣味程度: 邮递员阿飞今天第一天上班.下午,他要给华力小镇的四户人家投递信件.华力小镇住着四户相邻的人家,这几户人家经常在一起聚会. 阿飞来到华力小镇,发现信上的地址不全,他只能敲开其中一户人家的门,问问更详细的情况. 这天,这四户人家正好在聚会.小凯打开门,发现是一位新来的邮递员,她决定考...     

Finding Postal Carrier Walk Paths in Mixed Graphs

The postman problem requires finding a lowest cost tour in a connected graph that traverses each edge at least once. In this paper we first give a brief survey of the literature on postman problems including, the original Chinese postman problem on undirected graphs, the windy Chinese postman problem on graphs where the cost of an arc depends on the direction the arc is transversed, the directed postman problem on graphs with directed edges, and the mixed postman problem on graphs in which there are some directed and some undirected arcs.We show how the mixed postman problem can be solved as an integer program, using the formulation of Gendreau, Laporte and Zhao, by a new row addition branch and bound algorithm, which is a modification of the column subtraction algorithm for set partitioning problems of Harche and Thompson. Computational experience shows that a slack variable heuristic is very effective in finding good solutions that are frequently optimal for these problems.     

Four problems on graphs with excluded minors

The four problems we consider are the Chinese postman, odd cut, co-postman, and odd circuit problems. Seymour's characterization of matroids having the max-flow min-cut property can be specialized to each of these four problems to show that the property holds whenever the graph has no certain excluded minor. We develop a framework for characterizing graphs not having these excluded minors and use the excluded minor characterizations to solve each of the four optimization problems. In this way, a constructive proof of Seymour's theorem is given for these special cases. We also show how to solve the Chinese postman problem on graphs having no four-wheel minor, where the max-flow min-cut property need not hold.     

Series-parallel graphs are windy postman perfect

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph G, we consider the polyhedron O(G) induced by a linear programming relaxation of the windy postman problem. We say that G is windy postman perfect if O(G) is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. By considering a family of polyhedra related to O(G), we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of Win.     

Covering partially directed graphs with directed paths

We consider graphs which contain both directed and undirected edges (partially directed graphs). We show that the problem of covering the edges of such graphs with a minimum number of edge-disjoint directed paths respecting the orientations of the directed edges is polynomially solvable. We exhibit a good characterization for this problem in the form of a min-max theorem. We introduce a more general problem including weights on possible orientations of the undirected edges. We show that this more general weighted formulation is equivalent to the weighted bipartite b-factor problem. This implies the existence of a strongly polynomial algorithm for this weighted generalization of Euler's problem to partially directed graphs (compare this with the negative results for the mixed Chinese postman problem). We also provide a compact linear programming formulation for the weighted generalization that we propose.     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

An Eulerian exposition

An overview of Eulerian graphs is presented. In particular, characterizations of Eulerian graphs and digraphs as well as algorithms for constructing Eulerian circuits are discussed. A solution to the Chinese postman problem is followed by a study of subgraphs and supergraphs of Eulerian graphs. After an introduction to randomly Eulerian graphs and digraphs, we conclude with a summary of a variety of results involving enumeration.     

On the equivalence between some local and global Chinese postman and traveling salesman graphs

A connected graph G=(V,E), a vertex in V and a non-negative weight function defined on E can be used to induce Chinese postman and traveling salesman (cooperative) games. A graph G=(V,E) is said to be locally (respectively, globally) Chinese postman balanced (respectively, totally balanced, submodular) if for at least one vertex (respectively, for all vertices) in V and any non-negative weight function defined on E, the corresponding Chinese postman game is balanced (respectively, totally balanced, submodular). Local and global traveling salesman balanced (respectively, totally balanced, submodular) graphs are similarly defined.In this paper, we study the equivalence between local and global Chinese postman balanced (respectively, totally balanced, submodular) graphs, and between local and global traveling salesman submodular graphs.     

Postman problems on series–parallel mixed graphs

Given a strongly connected, mixed graph with costs on its edges and arcs, the mixed postman problem is to find a minimum cost closed walk traversing its edges and arcs at least once. This problem is NP-hard even on planar graphs but is solvable in polynomial time on series–parallel graphs. We give $O\left(n{m}^2\right)$ dynamic programming algorithms for the mixed postman problem and other similar problems on series–parallel graphs with $n$ vertices and $m$ edges and arcs.