中国邮递员问题50年

首先介绍一般邮递员问题, 涉及费用、服务侧、衔接费用、次序等要素. 然后简要综述过去50年来中国邮递员问题、有向图上中国邮递员问题、带风向的邮递员问题、混合图上邮递员问题以及乡村邮递员问题等一般邮递员问题的特殊情况的研究进展, 突出问题的线性规划描述及相应的组合多面体结构, 着重讨论问题的模型、精确算法及其时间复杂度、NP-困难情形下的近似算法及其性能比.     

On the generalized directed rural postman problem

The generalized directed rural postman problem (GDRPP) is a generic type of arc routing problem. In the present paper, it is described how many types of practically relevant single-vehicle routing problems can be modelled as GDRPPs. This demonstrates the versatility of the GDRPP and its importance as a unified model for postman problems. In addition, an exact and a heuristic solution method are presented. Computational experiments using two large sets of benchmark instances are performed. The results show high solution quality and thus demonstrate the practical usefulness of the approach.     

The rural postman problem with deadline classes

Vehicle routing problems with general time windows are extremely difficult to solve. However, the time windows in a particular problem may have a special structure which can be exploited. We consider a single-vehicle arc-routing problem in which the arcs are partitioned into deadline classes. It is shown that a cutting-plane approach works well for this problem.     

Binary group and Chinese postman polyhedra

A new proof of the characterization of the Chinese postman polyhedra is given. In developing this proof, a theorem of Gomory about homomorphic lifting of facets for group polyhedra is generalized to subproblems. Some results for the Chinese postman problem are generalized to binary group problems. In addition, a connection is made between Fulkerson's blocking polyhedra and a blocking pair of binary group problems. A connection is also developed between minors and lifting of facets for group problems.     

Matching,Euler tours and the Chinese postman

The solution of the Chinese postman problem using matching theory is given. The convex hull of integer solutions is described as a linear programming polyhedron. This polyhedron is used to show that a good algorithm gives an optimum solution. The algorithm is a specialization of the more generalb-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed.     

Cost allocation in asymmetric trees

Agents are connected each other through a tree. Each link of the tree has an associated cost and the total cost of the tree must be divided among the agents. In this paper we assume that agents are asymmetric (think on countries that use aqueducts to bring water from the rainy regions to the dry regions, for example). We suppose that each agent is entitled with a production and demand of a good that can be sent through the tree. This heterogeneity implies that the links are not equally important for all the agents. In this work we propose, and characterize axiomatically, two rules for sharing the cost of the tree when asymmetries apply.     

Cost allocation in inventory transportation systems

In this paper, we deal with the cost allocation problem arising in an inventory transportation system with a single item and multiple agents that place joint orders using an EOQ policy. In our problem, the fixed-order cost of each agent is the sum of a first component (common to all agents) plus a second component which depends on the distance from the agent to the supplier. We assume that agents are located on a line route, in the sense that if any subgroup of agents places a joint order, its fixed cost is the sum of the first component plus the second component of the agent in the group at maximal distance from the supplier. For these inventory transportation systems, we introduce and characterize a rule which allows us to allocate the costs generated by the joint order. This rule has the same flavor as the Shapley value, but requires less computational effort. We show that our rule has good properties from the point of view of stability.     

Cost allocation in collaborative forest transportation

Transportation planning is an important part of the supply chain or wood flow chain in forestry. There are often several forest companies operating in the same region and collaboration between two or more companies is rare. However, there is an increasing interest in collaborative planning as the potential savings are large, often in the range 5–15%. There are several issues to agree on before such collaborative planning can be used in practice. A key question is how the total cost or savings should be distributed among the participants. In this paper, we study a large application in southern Sweden with eight forest companies involved in a collaboration. We investigate a number of sharing mechanisms based on economic models including Shapley value, the nucleolus, separable and non-separable costs, shadow prices and volume weights. We also propose a new allocation method, with the aim that the participants relative profits are as equal as possible. We use two planning models, the first is based on direct flows between supply and demand points and the second includes backhauling. We also study how several time periods and geographical distribution of the supply and demand nodes affect the solutions. Better planning within each company can save about 5% and collaboration can increase this about another 9% to a total of 14%. The proposed allocation method is shown to be a practical approach to share the overall cost/savings.     

On the max‐cut problem for a planar,cubic, triangle‐free graph,and the Chinese postman problem for a planar triangulation

Every 3‐connected planar, cubic, triangle‐free graph with n vertices has a bipartite subgraph with at least 29n/24 ? 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Examples show that the constant 29/24 = 1.2083… cannot be raised to more than 47/38 = 1.2368…. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 261–269, 2006     

Cost allocation in a bank ATM network

We consider a situation in which a group of banks consider connecting their Automated Teller Machines (ATMs) in a network, so that the banks customers may use ATMs of any bank in the network. The problem studied is that of allocating the total transaction costs arising in the network, among the participating banks. The situation is modeled as a cooperative game with transferable utility. We propose two allocations, and discuss their relation to the core and other well-known solution concepts, as well as to population monotonicity.Endre Bjørndal has enjoyed the hospitality of Tilburg University, and has also received financial support from Telenor AS and the Norwegian School of Economics and Business Administration.     

Cost allocation and convex data envelopment

This paper considers allocation rules. First, we demonstrate that costs allocated by the Aumann–Shapley and the Friedman–Moulin cost allocation rules are easy to determine in practice using convex envelopment of registered cost data and parametric programming. Second, from the linear programming problems involved it becomes clear that the allocation rules, technically speaking, allocate the non-zero value of the dual variable for a convexity constraint on to the output vector. Hence, the allocation rules can also be used to allocate inefficiencies in non-parametric efficiency measurement models such as Data Envelopment Analysis (DEA). The convexity constraint of the BCC model introduces a non-zero slack in the objective function of the multiplier problem and we show that the cost allocation rules discussed in this paper can be used as candidates to allocate this slack value on to the input (or output) variables and hence enable a full allocation of the inefficiency on to the input (or output) variables as in the CCR model.     

Cost allocation games with information costs

We propose a simple model which embeds cost allocation games into a richer structure to take into account that information on costs can be itself costly. The model is an outgrowth of experience on cost allocation for consortia of municipalities dealing with garbage collection.The authors thank an anonymous referee for having pointed out a mistake in the previous version of Lemma 1     

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.