Improving routing and scheduling decisions at a distributor of industrial gasses

This paper investigates cyclical inventory replenishment for a company's regional distribution center that supplies, distributes, and manages inventory of carbon dioxide (_CO2)$({\mathrm{CO}}_2)$ at over 900 separate customer sites in Indiana. The company previously experienced high labor costs with excessive overtime and maintained a regular back-log of customers experiencing stockouts. To address these issues we implemented a three-phase heuristic for the cyclical inventory routing problem encountered at one of the company's distribution centers. This heuristic determines regular routes for each of three available delivery vehicles over a 12-day delivery horizon while improving four primary performance measures: delivery labor cost, stockouts, delivery regularity, and driver–customer familiarity. It does so by first determining three sets of cities (one for each delivery vehicle) that must be delivered to each day based on customer requirements. Second, the heuristic assigns the remaining customers in other cities to one of the three “backbone routes” determined in phase 1. And third, it balances customer deliveries on each daily route over the schedule horizon. Through our methodology, we were able to significantly reduce overtime, driving time, and labor costs while improving customer service.     

The robustness of linear models for decision-making

This paper elaborates on some issues discussed by Moskowitz, who presented evidence that linear multiple regression models, estimated from decisions made by individuals, often outperform the individuals themselves. In discussing his results, Moskowitz (1) suggested that inconsistency in information utilization by individuals may account for the relative superiority of regression models, and (2) expressed concern over the robustness of linear regression models to changes in (a) information environments, (b) weighting parameters, and (c) functional form of the model. This paper discusses reasons (in addition to inconsistency) for the relative superiority of model over man, and it summarizes recent research in psychology concerning the robustness of linear regression models (and linear models in general). This paper is supportive, rather than critical, of Moskowitz's research.     

The subdivision-constrained routing requests problem

We are given a digraph D=(V,A;w), a length (delay) function w:A→R ⁺, a positive integer d and a set $\mathcal{P}=\{(s_{i},t_{i};B_{i}) | i=1,2,\ldots,k\}$ of k requests, where s _i ∈V is called as the ith source node, t _i ∈V is called the ith sink node and B _i is called as the ith length constraint. For a given positive integer d, the subdivision-constrained routing requests problem (SCRR, for short) is to find a directed subgraph D′=(V′,A′) of D, satisfying the two constraints: (1) Each request (s _i ,t _i ;B _i ) has a path P _i from s _i to t _i in D′ with length $w(P_{i})=\sum_{e\in P_{i}} w(e)$ no more than B _i ; (2) Insert some nodes uniformly on each arc e∈A′ to ensure that each new arc has length no more than d. The objective is to minimize the total number of the nodes inserted on the arcs in A′. We obtain the following three main results: (1) The SCRR problem is at least as hard as the set cover problem even if each request has the same source s, i.e., s _i =s for each i=1,2,…,k; (2) For each request (s,t;B), we design a dynamic programming algorithm to find a path from s to t with length no more than B such that the number of the nodes inserted on such a path is minimized, and as a corollary, we present a k-approximation algorithm to solve the SCRR problem for any k requests; (3) We finally present an optimal algorithm for the case where $\mathcal{P}$ contains all possible requests (s _i ,t _i ) in V×V and B _i is equal to the length of the shortest path in D from s _i to t _i . To the best of our knowledge, this is the first time that the dynamic programming algorithm within polynomial time in (2) is designed for a weighted optimization problem while previous optimal algorithms run in pseudo-polynomial time.     

Modelling process robustness: a case study of centrifugal casting

A robust process minimises the effect of the noise factors on the performance of a product or process. The variation of the performance of a robust process can be measured through modelling and analysis of process robustness. In this paper, a comprehensive methodology for modelling and analysis of process robustness is developed considering a number of relevant tools and techniques such as multivariate regression, control charting and simulation within the broad framework of Taguchi method. The methodology as developed considers, in specific terms, process modelling using historical data pertaining to responses, inputs variables and parameters as well as simulated noise variables data, identification of the model responses at each experimental setting of the controllable variables, estimation of multivariate process capability indices and control of their variability using control charting for determining optimal settings of the process variables using design of experiment-based Taguchi Method. The methodology is applied to a centrifugal casting process that produces worm-wheels for steam power plants in view of its critical importance of maintaining consistent performance in various under controllable situations (input conditions). The results show that the process settings as determined ensure minimum in-control variability with maximum performance of the centrifugal casting process, indicating improved level of robustness.     

关联供应链网络级联失效机理及鲁棒性研究

为了分析复杂关联供应链网络在遭遇干扰事件时的鲁棒性,研究关联网络层内和层间级联失效机理.通过随机规则生成供应链无向信息层网络和有向物理层网络,描述并分析由α、β、σ等参数表征的节点负荷、容量等网络结构特性.针对存在边流量约束的情况,提出相应的失效负荷分流策略;通过构建极大簇函数,判断关联供应链网络中经分流策略后仍具运作功能的有效节点,并依据供应链信息层网络和物理层网络间一对一匹配的关联关系,构建时变失效迭代状态方程,从而有效描述关联网络间的动态失效传递.最后,在不同参数控制下,对初始单个节点故障和多个节点故障两种情况下的关联供应链网络综合鲁棒性进行数值仿真分析.按节点度从大到小、从小到大、随机3种方式去除多个节点,结果表明在β=0.5, 1, 1.5, 2 4种参数下,按度从小到大方式去除多节点,其引发的关联网络级联失效规模较之其它两种方式大;同时发现关联供应链网络在多节点去除情况下,其级联失效较之单层网络具有明显的一级相变特性,即少量的节点移除就会导致整个关联供应链网络崩溃.     

A robustness framework for monitoring real options under uncertainty

This paper presents a problem structuring methodology to assess real option decisions in the face of unpredictability. Based on principles of robustness analysis and scenario planning, we demonstrate how decision-aiding can facilitate participation in projects setting and achieve effective decision making through the use of real options reasoning. We argue that robustness heuristics developed in earlier studies can be practical proxies for real options performance, hence indicators of efficient flexible planning. The developed framework also highlights how to integrate real options solutions in firms’ strategic plans and operating actions. The use of the methodology in a location decision application is provided for illustration.     

The price of atomic selfish ring routing

We study selfish routing in ring networks with respect to minimizing the maximum latency. Our main result is an establishment of constant bounds on the price of stability (PoS) for routing unsplittable flows with linear latency. We show that the PoS is at most 6.83, which reduces to 4.57 when the linear latency functions are homogeneous. We also show the existence of a (54,1)-approximate Nash equilibrium. Additionally we address some algorithmic issues for computing an approximate Nash equilibrium.     

城市交通中车辆择路行为实证研究

随机、时变的交通流分布,偶发的交通事故等因素导致了路径随机的车辆旅行时间,也决定了现实城市交通网络中只存在随机最短路.已有的路径选择研究大都假设人们力求选择最短路,而通过实际调查发现:人们的择路行为依赖出行情景,随出行目的、约束时间、对路径的熟悉程度以及路径的不确定程度而变化.验证了城市交通中人们在不确定环境下的择路行为也符合展望理论.     

A continuous-time supply-driven inventory-constrained routing problem

We address an inventory routing problem (IRP) in which routing and inventory decisions are dictated by supply rather than demand. Moreover, inventory is held in containers that act as both a storage container and a movable transport unit. This problem emanates from logistics related to biogas transportation in which biogas is transported in containers from many suppliers to a single facility. We present a novel and compact formulation for the supply-driven IRP which addresses the routing decisions in continuous-time in which inventory levels within the containers are continuous. Valid inequalities are included and realistic instances are solved to optimality. For all experiments, we found that the total transportation time is minimized when the storage capacity at each supplier is larger than or equal to the vehicle capacity. These routes are characterized by tours in which mostly single suppliers are visited. In 95% of the instances, the average content level of the exchanged containers exceeded 99.6%.     

Vehicle routing using fixed delivery areas

In this paper we consider the problem of vehicle routing using fixed delivery areas. This is the problem of splitting the area serviced by a depot into a number of separate subareas—a single delivery vehicle being assigned to each subarea to supply all the customers within the subarea. A heuristic algorithm is developed for the problem based upon an initial allocation of customers to subareas followed by customer interchanges in an attempt to improve the subareas. Computational results are presented for a number of test problems drawn from the literature.     

Supply vessel planning under cost,environment and robustness considerations

Offshore oil and gas installations need reliable cargo deliveries. The vessels supplying these installations on a periodic basis are expensive and constitute a source of emissions of greenhouse gases. Incorporating vessel speed optimization into the supply vessel planning process may significantly reduce fuel consumption and hence emissions. In addition, speed optimization may yield cost reductions if the number of vessels used does not increase. A main uncertainty factor, especially in the winter season, is the weather conditions which impact sailing and service times. Cost minimization and the application of speed optimization strategies may have implications on the robustness of weekly supply vessel schedules since idle times in the schedules are reduced. We develop a simulation-optimization based methodology that considers costs, emissions and robustness in the generation of weekly supply vessel schedules. Results of analyses conducted on real instances show that robustness requirements may yield both increased emissions and costs in the winter season. However, depending on instance characteristics, different degrees of robustness can be incorporated with both costs and emissions reductions through speed optimization.     

带货物权重的车辆路径问题及遗传算法

考虑一个分销中心、多个零售商组成的分销网络系统中具有柔性车辆能力的带货物权重的车辆路径问题.并根据车辆的满载情况采用了不同的运输策略,即单点运输和多点运输方式.在多点运输方式下,与以往诸多研究不同的是,文章建立了一种基于货物权重的VRP模型——WVRP,即在安排车辆线路时每个零售商的货物需求量也作为一个因素考虑,尽可能使车辆优先供货需求量较大的零售商.最后,针对问题的性质,开发了一种基于划分的遗传算法PB-GA对问题进行求解,并与一般遗传算法及常用的启发式算法进行了分析比较.     

Using vulnerability performance indicators to attain food supply chain robustness

High effectiveness and leanness of modern supply chains (SCs) increase their vulnerability, i.e. susceptibility to disturbances reflected in non-robust SC performances. Both the SC management literature and SC professionals indicate the need for the development of SC vulnerability assessment tools. In this article, a new method for vulnerability assessment, the VULA method, is presented. The VULA method helps to identify how much a company would underperform on a specific Key Performance Indicator in the case of a disturbance, how often this would happen and how long it would last. It ultimately informs the decision about whether process redesign is appropriate and what kind of redesign strategies should be used in order to increase the SC's robustness. The applicability of the VULA method is demonstrated in the context of a meat SC using discrete-event simulation to conduct the performance analysis.     

On weak Pareto optimality of nonatomic routing networks

Journal of Combinatorial Optimization - This paper establishes several sufficient conditions for the weak Pareto optimality of Nash equilibria in nonatomic routing games on single- and...     

An illustration of dynamic network DEA in commercial banking including robustness tests

The main motivation of this article is to illustrate dynamic network data envelopment analysis (DN-DEA) in commercial banking with emphasis on testing robustness. To this end, sixteen foreign banks in China are benchmarked against thirty-two domestic banks for the post-2007 period that follows major reforms. When network and dynamic dimensions are brought together, a more comprehensive analysis of the period 2008–2010 is enabled where divisional and between-period interactions are reflected in efficiency estimates. Weighted, variable returns-to-scale, non-oriented dynamic network slacks-based measure is used within the framework of the intermediation approach to bank behavior. A bank network (i.e., a decision-making unit, DMU) is conceptualized as comprised of two divisions or sub-DMUs, namely, interest-bearing operations and non-interest operations linked by number of referrals. Undesirable outputs from sub-DMUs 1 and 2 (non-performing loans, and proportion of fruitless referrals, respectively) are treated as carry-overs that impact the efficiency of the following periods. Under robustness testing, the illustrative application discusses discrimination by efficiency estimates, dimensionality of the performance model, stability of estimates through re-sampling (leave-one-out method), and sensitivity of results to divisional weights and returns-to-scale assumptions. The results based on Chinese commercial banks are illustrative in nature because of simulated data used on two of the variables.     

Inapproximability and approximability of maximal tree routing and coloring

Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability of this problem and prove Ω(g^1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds. Supported in part by the NSF of China under Grant No. 70221001 and 60373012.     

Locations and vehicle routing designs of physical distribution systems

The design of a physical distribution system (PDS) involves the determination of the number and locations of distribution centres, estimation of required vehicle numbers and design of vehicle routings. Due to the enormous numbers of possible combinatorial designs of the system, it is difficult to obtain an optimal design in acceptable computation effort on many occasions. In this paper, a new solution framework for the design of PDS by implementing the genetic algorithm (GA) is presented. With the characteristic of simultaneous optimization of a large population of configuration, the proposed methodology has been proved to be an extremely efficient optimizer. In the experimental simulation conducted in this paper, it also indicates this approach can provide a near-optimal solution to the design of PDS. To analyse the growth and decay of many schemas contained in the population, the effects of the operation of reproduction, crossover and mutation on the schema are studied. The simulation evaluation about the system performance and genetic parameters is presented along with the discussions at the end of this paper.     

On the minimum routing cost clustered tree problem

For an edge-weighted graph \(G=(V,E,w)\), in which the vertices are partitioned into k clusters \(\mathcal {R}=\{R_1,R_2,\ldots ,R_k\}\), a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing \(k-1\) edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for \(k=3\). Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.     

The technician routing problem with experience-based service times

While home services are a fast growing industry, little attention has been given to the management of its workforce. In particular, the productivity of home-service technicians depends not only on efficiently routing from customer-to-customer, but also the management of their skillsets. This paper introduces a model of technician routing that explicitly models individualized, experience-based learning. The results demonstrate that explicit modeling and the resulting ability to capture changes in productivity over time due to learning lead to significantly better and different solutions than those found when learning and workforce heterogeneity is ignored. We show that these differences result from the levels of specialization that occur in the workforce.