一种改进的TSP问题启发式算法

旅行推销商问题(TSP)属于组合优化领域中一个典型的NP Hard问题。本文在最近城市搜索法的基础上,提出一种改进的启发式算法———两端延伸最近城市搜索法,这种方法能够很快得到最优解(近优解),且大大降低了计算复杂度。同时,对TSP问题进行了分类,并给出相应的启发式解法。     

基于求解TSP问题的双向扩展差额算法

旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.     

Online covering salesman problem

Given a graph \(G=(V,E,D,W)\), the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex \(i\in D\) is either on the tour or within a predetermined distance L to an arbitrary vertex \(j\in W\) on the tour, where \(D\subset V\),\(W\subset V\). In this paper, we propose the online CSP, where the salesman will encounter at most k blocked edges during the traversal. The edge blockages are real-time, meaning that the salesman knows about a blocked edge when it occurs. We present a lower bound \(\frac{1}{1 + (k + 2)L}k+1\) and a CoverTreeTraversal algorithm for online CSP which is proved to be \(k+\alpha \)-competitive, where \(\alpha =0.5+\frac{(4k+2)L}{OPT}+2\gamma \rho \), \(\gamma \) is the approximation ratio for Steiner tree problem and \(\rho \) is the maximal number of locations that a customer can be served. When \(\frac{L}{\texttt {OPT}}\rightarrow 0\), our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived.     

A Specialized Inventory Problem in Banks: Optimizing Retail Sweeps

Deposits held at Federal Reserve Banks are an essential input to the business activity of most depository institutions in the United States. Managing these deposits is an important and complex inventory problem for two reasons. First, Federal Reserve regulations require that depository institutions hold certain amounts of such deposits at the Federal Reserve Banks to satisfy statutory reserve requirements against customers' transaction accounts (demand deposits and other checkable deposits). Second, some inventory of such deposits is essential for banks to operate one of their core lines of business: furnishing payment services to households and firms. Because the Federal Reserve does not pay interest on such deposits used to satisfy statutory reserve requirements, banks seek to minimize their inventory of such deposits. In 1994, the banking industry introduced a new inventory management tool for such deposits, the retail deposit sweep program, which avoids the statutory requirement by reclassifying transaction deposits as savings deposits. This is an interesting inventory problem for fungible items, where the conversion process is reversible. We examine two methods for operating such sweeps programs within the limits of Federal Reserve regulations, and we develop a stochastic dynamic programming model to implement one such method, the threshold method.     

The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation

In the prize-collecting travelling salesman problem, we are given a weighted graph \(G=(V,E)\) with edge weights \(\ell :E\rightarrow \mathbb {R}_+\), a special vertex \(r\in V\), penalties \(\pi :V\rightarrow \mathbb {R}_+\) and the goal is to find a closed tour \(T\) such that \(r\in V(T)\) and such that the cost \(\ell (T)+\pi (V\setminus V(T))\), which is the sum of the edges in the tour and the cost of the vertices not spanned by \(T\), is minimized. We consider an online variant of the prize-collecting travelling salesman problem related to graph exploration. In the Canadian Tour Operator Problem the task is to find a closed route for a tourist bus in a given network \(G=(V,E)\) in which some edges are blocked by avalanches. An online algorithm learns from a blocked edge only when reaching one of its endpoints. The bus operator has the option to avoid visiting each node \(v\in V\) by paying a refund of \(\pi (v)\) to the tourists. The goal consists of minimizing the sum of the travel costs and the refunds. We study the problem on a simple (weighted) path and prove tight bounds on the competitiveness of deterministic algorithms. Specifically, we give an algorithm with competitive ratio equal to the golden ratio \(\phi =(1+\sqrt{5})/2\). We also study the effect of resource augmentation, where the online algorithm either pays a discounted cost for traversing edges or for the penalties.     

A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP

We present a primal-dual ?log(n)?-approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. The previous algorithm for the problem (V.H. Nguyen and T.T Nguyen in Int. J. Math. Oper. Res. 4(3):294–301, 2012) which is not combinatorial, is based on the Held-Karp relaxation and heuristic methods such as the Frieze et al.’s heuristic (Frieze et al. in Networks 12:23–39, 1982) or the recent Asadpour et al.’s heuristic for the ATSP (Asadpour et al. in 21st ACM-SIAM symposium on discrete algorithms, 2010). Depending on which of the two heuristics is used, it gives respectively 1+?log(n)? and $3+ 8\frac{\log(n)}{\log(\log(n))}$ as an approximation ratio. Our algorithm achieves an approximation ratio of ?log(n)? which is weaker than $3+ 8\frac{\log(n)}{\log(\log(n))}$ but represents the first combinatorial approximation algorithm for the Asymmetric Prize-Collecting TSP.     

Combinatorial analysis for route first-cluster second vehicle routing

Two Route first-cluster second vehicle routing algorithms are contrasted in the first section of the paper. Next, the ‘large’ number of feasible solutions to a multiple travelling salesman problem is established given that each salesman can visit any number of customers in a stated range. An approximate expression is given for the ‘small’ fraction of this solution space searched by a route first-cluster second vehicle routing heuristic. Nevertheless, this heuristic is seen to be a very efficient means of searching its solution space.     

问题导向：管理理论发展的推动力

问题是理论研究的起点.在人类管理理论时代性贡献与实践性关系上, 主要的困难不是答案, 而是问题.真正有价值的实际问题既能使管理理论具有旺盛的生命力, 又能使管理理论保持与时俱进的鲜活度, 并且理论的学术价值与真理性最终只能用解决实际问题的实践来证明.反之, 长久地脱离生动的管理问题, 忘记实践本身就是伟大的思想者, 或者一味生活在别人的思想栅栏和理论围城中, 终究会使我们自己的学术生命力慢慢衰落.问题导向原则要求我国管理理论研究不仅坚持实践化, 更从本国国情出发, 以解决我国现实问题和指导我国管理实践为主旨, 最终推动管理学术中国化的实现.当前需要认真弄清楚这一学理逻辑的基本形态与范式, 弄清楚如何在问题导向原则中保持这种形态的持久张力, 并使这种形态超越民族与地域的局限而融入人类管理学术整体文明之中.     

The optimum traversal of a graph

For a given graph (network) having costs [c_ij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity q_ij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc.     

Lexicographically minimizing axial motions for the Euclidean TSP

A variant of the Euclidean traveling salesman problem (TSP) is defined and studied. In the three-dimensional space, the objective function is to lexicographically minimize the x-moves, then the y-moves and finally the z-moves. The 2D and 3D cases are first studied and solved as a shortest path problem. Then the approach is generalized to the d-dimensional case.     

The multiple traveling salesman problem: an overview of formulations and solution procedures

The multiple traveling salesman problem (mTSP) is a generalization of the well-known traveling salesman problem (TSP), where more than one salesman is allowed to be used in the solution. Moreover, the characteristics of the mTSP seem more appropriate for real-life applications, and it is also possible to extend the problem to a wide variety of vehicle routing problems (VRPs) by incorporating some additional side constraints. Although there exists a wide body of the literature for the TSP and the VRP, the mTSP has not received the same amount of attention. The purpose of this survey is to review the problem and its practical applications, to highlight some formulations and to describe exact and heuristic solution procedures proposed for this problem.     

A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, ), which is an improvement over the existing 1.5-approximation.     

TOURING A SUPPLY CHAIN WITH STUDENTS: PEDAGOGICAL AND PRACTICAL CONSIDERATIONS

This paper describes the supply chain tour, an expansion of the widely used facility tour pedagogy. A supply chain tour is a tour of facilities sequentially related in the creation of value that is designed to expose critical linkages and illustrate Supply Chain Management concepts and theories. Effectively using the supply chain tour pedagogy requires the instructor to create a standardized approach to managing the facility tour; a checklist is provided for this purpose. An example supply chain tour, used in the author's classes, is described.     

Satisfaction with Virtual Communities of Interest: Effect on Members' Visit Frequency*

The authors develop a four‐dimensional scale to measure members' satisfaction with virtual communities of interest (VCIs). The dimensions consist of members' satisfaction with member‐to‐member interactions, organizer‐to‐member interactions and organizer‐to‐community interactions, all of which come together on the VCI's site. Using a sample of 3605 members of a VCI, the authors investigated the effect of each satisfaction dimension on members' visit frequency, and the moderating effect of membership duration on the links between the satisfaction dimensions and visit frequency. The results reveal that satisfaction with member‐to‐member interactions, organizer‐to‐member interactions and the community's site has positive effects on members' visit frequency. Members' satisfaction with organizer‐to‐community interactions has no effect on visit frequency. The findings also show that membership duration strengthens two, and weakens one of the linkages between the satisfaction dimensions and members' visit frequency.     

Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.     

MULTICRITERIA OPTIMIZATION: A GENERAL CHARACTERIZATION OF EFFICIENT SOLUTIONS*

In the context of deterministic multicriteria maximization, a Pareto optimal, nondominated, or efficient solution is a feasible solution for which an increase in value of any one criterion can only be achieved at the expense of a decrease in value of at least one other criterion. Without restrictions of convexity or continuity, it is shown that a solution is efficient if and only if it solves an optimization problem that bounds the various criteria values from below and maximizes a strictly increasing function of these several criteria values. Also included are discussions of previous work concerned with generating or characterizing the set of efficient solutions, and of the interactive approach for resolving multicriteria optimization problems. The final section argues that the paper's main result should not actually be used to generate the set of efficient solutions, relates this result to Simon's theory of satisficing, and then indicates why and how it can be used as the basis for interactive procedures with desirable characteristics.     

The Newsvendor Problem and Price‐Only Contract When Bankruptcy Costs Exist

We study a supply chain of a supplier selling via a wholesale price contract to a financially constrained retailer who faces stochastic demand. The retailer might need to borrow money from a bank to execute his order. The bank offers a fairly priced loan for relevant risks. Failure of loan repayment leads to a costly bankruptcy (fixed administrative costs, costs proportional to sales, and a depressed collateral value). We identify the retailer's optimal order quantity as a function of the wholesale price and his total wealth (working capital and collateral). The analysis of the supplier's optimal wholesale price problem as a Stackelberg game, with the supplier the leader and the retailer the follower, leads to unique equilibrium solutions in wholesale price and order quantity, with the equilibrium order quantity smaller than the traditional newsvendor one. Furthermore, in the presence of the retailer's bankruptcy risks, increases in the retailer's wealth lead to increased supplier's wholesale prices, but without the retailer's bankruptcy risks the supplier's wholesale prices stay the same or decrease in retailer's wealth.     

下料问题与运输问题联合优化建模

本文研究了考虑子材运输的标准一维下料问题。建立了由生产商负责运输时,标准一维下料与运输协调优化整数规划模型,最小化母材使用成本,子材库存成本及子材运输成本。采用拉格朗日松弛技术对有关约束进行松弛和模型分解,设计基于序列规则和FFD规则的混合启发式算法求解模型。该算法由两部分组成,分别用于求解标准一维下料子问题和卖方运输子问题。通过随机产生的1800个算例,验证模型合理性与算法的有效性。与基于列生成法的两阶段算法解进行比较,平均总成本降低了17.57%,表明集成算法优于两阶段算法。     

A Promissory Theory of the Duty to Tip

In this article, I argued that in contexts in which tipping is customary, there is a moral duty to tip or to explicitly tell the server that you will not be tipping. The evidence for this rests on anecdotes about people's mental states, and customers and server's intuitions about duties that would arise were a customer unable to tip his server. The promise is a speech act that is implicit in ordering food. The speech act must be matched by the server's uptake, which is implicit in her taking the order. The promise argument rests on an actual promise and not a merely hypothetical promise. If there is such a duty, then in the absence of an explicit content, its content is likely set by convention. The convention is that customers tip 15–20%. Thus, customers have a duty to tip servers 15–20%. Other purported moral considerations do not ground this duty. These include custom, desirable incentives, role‐relative obligation, and gratitude.     

The Travelling Salesman Problem on Permuted Monge Matrices

We consider traveling salesman problems (TSPs) with a permuted Monge matrix as cost matrix where the associated patching graph has a specially simple structure: a multistar, a multitree or a planar graph. In the case of multistars, we give a complete, concise and simplified presentation of Gaikov's theory. These results are then used for designing an O(m3 + mn) algorithm in the case of multitrees, where n is the number of cities and m is the number of subtours in an optimal assignment. Moreover we show that for planar patching graphs, the problem of finding an optimal subtour patching remains NP-complete.