A visual interactive approach to classical and mixed vehicle routing problems with backhauls

In this paper a new visual interactive approach for the classical vehicle routing problem with backhauls (VRPB) and its extensions is presented. The classical VRPB is the problem of designing minimum cost routes from a single depot to two type customers that are known as Backhaul (pickup) and Linehaul (delivery) customers where deliveries after pickups are not allowed. The mixed VRPB is an extension of the classical VRPB where deliveries after pickups are allowed.     

A branch-and-price approach for trip sequence planning of high-speed train units

In high-speed railway operations, a trip sequence plan is made once the timetable is determined, and serves as a reference in the subsequent operations of train units scheduling. In light of the maintenance requirements of train units and periodicity characteristics of trip sequences, we introduce a trip sequence graph to describe the train units’ movement and coupling/splitting in a railway network. Based on the trip sequence graph, two integer linear programming models are then formulated, namely a path-based model and an arc-based model. Integrated with the characteristics of the trip sequence graph, a customized branch-and-price algorithm is developed to solve the path-based model. The two models are applied to the high-speed railway network in eastern China, and through numerical experiments, the effectiveness and applicability of the models are discussed.     

Reliable Ad Hoc Routing Based on Mobility Prediction

Reliability is a very important issue in Mobile Ad hoc NETworks (MANETs). Shortest paths are usually used to route packets in MANETs. However, a shortest path may fail quickly, because some of the wireless links along a shortest path may be broken shortly after the path is established due to mobility of mobile nodes. Rediscovering routes may result in substantial data loss and message exchange overhead. In this paper, we study reliable ad hoc routing in the urban environment. Specifically, we formulate and study two optimization problems. In the minimum Cost Duration-bounded Path (CDP) routing problem, we seek a minimum cost source to destination path with duration no less than a given threshold. In the maximum Duration Cost-bounded Path (DCP) routing problem, we seek a maximum duration source to destination path with cost no greater than a given threshold. We use a waypoint graph to model the working area of a MANET and present an offline algorithm to compute a duration prediction table for the given waypoint graph. An entry in the duration prediction table contains the guaranteed worst-case duration of the corresponding wireless link. We then present an efficient algorithm which computes a minimum cost duration-bounded path, using the information provided in the duration prediction table. We also present a heuristic algorithm for the DCP routing problem. In addition, we show that the proposed prediction and routing schemes can be easily applied for designing reliable ad hoc routing protocols. Simulation results show that our mobility prediction based routing algorithms lead to higher network throughput and longer average path duration, compared with the shortest path routing. This research was supported in part by ARO grant W911NF-04-1-0385 and NSF grant CCF-0431167. The information reported here does not reflect the position or the policy of the federal government.     

基于平均最小间隔的城际铁路线路运输能力计算模型

在城市群交通一体化迅速发展的大背景下,本文针对城际铁路的运输能力计算问题提出一种与之相适应的计算模型。首先,文章在分析城际铁路运营特点基础上,基于整数线性规划建立计算模型,该模型利用平均最小间隔时间法中将两列相邻的列车组合为运行列车组作为运行图结构单元的思想来计算列车占用运行图总时间,并以最大化运行列车组总数为目标函数,以规定列车占用运行图总时间的有效时间范围为约束条件。最后,文章通过京津城际实际数据算例,验证了文章所提计算模型相较于传统计算方法更切合城际铁路运营实际。该模型大幅简化了城际铁路线路运输能力的计算步骤,提高了计算效率,能够助力于改善城际铁路运输能力及其运营服务水平。     

An exact micro–macro approach to cyclic and non-cyclic train timetabling

When planning new railway infrastructures in order to enhance the network to meet future demand, the capacity departments of railway operators typically have to face a time consuming trial-and-error process. The process involves the computation of a new timetable which satisfies the demand and is feasible w.r.t. the enhanced network, and is typically carried out by expert personnel with little or no assistance by computer tools. The quality of the results is thus very dependent on the skills of the individual planner. In this paper, we describe an exact approach to produce train timetables in short computation time. The approach extends the models and decomposition algorithms previously developed for train dispatching, a deeply related operational problem. The problem is solved at the microscopic level and the final timetable, even if in general non-cyclic, can incorporate cyclicity constraints for any subset of trains. Results are presented for a feasibility study in the Oslo area commissioned by the capacity planning department at Jernbaneverket (Norway׳s infrastructure manager).     

The Tradeoffs Associated with Rerouting Highway Shipments of Hazardous Materials to Minimize Risk

Recent legislative and regulatory activities at the federal level have focused attention on the highway routing of hazardous materials. The question is whether routes that minimize the risk of release accidents (i.e., the expected number of persons impacted by releases of hazardous materials) should be used in lieu of the routes that have the lowest operating costs. This policy issue is addressed for interstate shipments by using a national network model to determine the practical route and minimum risk route between each of 100 different origin-destination pairs (state capitals). The resulting cost-risk tradeoffs are then used to estimate the average cost of rerouting per fatality averted, the value of which turns out to be within the range of values for a number of familiar existing regulations.     

Multi-depot vessel routing problem in a direction dependent wavefield

Considerable research has been done on the vehicle routing problem and its variants; however only limited amount of existing work deals with possible environmental conditions and their effects on the vehicle routes. This paper presents the multiple-depot vehicle routing problem for surface vessels, where the vehicles must traverse a time-invariant direction-dependent medium. Our model captures environmental effects and vessel dynamics on the considered paths. Three heuristic solution methods are developed and tested on simulated scenarios. The first approach exactly solves an approximate formulation of the problem, the second approximately solves an approximate problem formulation, while the third approximately solves the exact problem. Performance of the algorithms are compared to assess the tradeoff between computational cost and quality of the found solutions.     

考虑充电策略与电池损耗的电动汽车路径优化问题研究

针对目前研究电动物流车辆路径问题的文章未考虑电池损耗对运营成本的影响,且多在充电速率为恒定值的情况下对充电策略进行优化,本文将电动物流车辆在配送货物途中的充电时间和电池损耗成本纳入目标函数并建立了线性规划数学模型,统筹安排车辆行驶路径和充电策略使得物流企业整体运营成本最低。其次,提出了求解该问题的多阶段启发式算法MCWIGALNS。随后,通过多组算例验证了模型和算法的准确性。实验结果表明,考虑充电时间与深度放电成本的模型可以在配送距离不变或略有增加的情况下,较大幅度减少充电时间与电池损耗成本,到达降低运营成本的目的。最后,将算法实验结果与本领域已发表的成果进行比较,证明了MCWIGALNS算法对车辆路径问题具有出色的求解能力,提升了该问题理论成果的实用性。可以为物流企业电动汽车路径策略提供良好借鉴与帮助。     

Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics

This paper addresses a periodic vehicle routing problem encountered in home health care (HHC) logistics. It extends the classical Periodic Vehicle Routing Problem with Time Windows (PVRPTW) to three types of demands of patients at home. Demands include transportation of drugs/medical devices between the HHC depot and patients׳ homes, delivery of special drugs from the hospital to patients, and delivery of blood samples from patients to the lab. Each patient requires a certain number of visits within a planning horizon and has a set of possible combinations of visit days. Daily routing should meet time window constraints associated with patients, the hospital and the lab. The problem consists in determining the visit days of each patient and vehicle routes for each day in order to minimize the maximal routing costs among all routes over the horizon. We propose a Tabu Search method combined with different local search schemes including both feasible and infeasible local searches. The proposed approaches are tested on a range of instances derived from existing Vehicle Routing Problem with Time Window (VRPTW) benchmarks and benchmarks on special cases of our problem. Numerical results show that local search scheme starting with an infeasible local search with a small probability followed by a feasible local search with high probability is an interesting hybridization. Experiments with field data from a HHC company show that the proposed approach reduces the total cost and better balances the workloads of vehicles.     

Integrated planning of inbound and outbound logistics with a Rich Vehicle Routing Problem with backhauls

This paper addresses the integration of the planning decisions concerning inbound logistics in an industrial setting (from the suppliers to the mill) and outbound logistics (from the mill to customers). The goal is to find the minimum cost routing plan, which includes the cost-effective outbound and inbound daily routes (OIRs), consisting of a sequence of deliveries of customer orders, pickup of a full truck-load at a supplier, and its delivery to the mill. This study distinguishes between three planning strategies: opportunistic backhauling planning (OBP), integrated inbound and outbound planning (IIOP) and decoupled planning (DIOP), the latter being the commonly used, particularly in the case of the wood-based panel industry under study. From the point of view of process integration, OBP can be considered as an intermediate stage from DIOP to IIOP. The problem is modelled as a Vehicle Routing Problem with Backhauls, enriched with case-specific rules for visiting the backhaul, split deliveries to customers and the use of a heterogeneous fleet. A new fix-and-optimise matheuristic is proposed for this problem, seeking to obtain good quality solutions within a reasonable computational time. The results from its application to the wood-based panel industry in Portugal show that IIOP can help to reduce total costs in about 2.7%, when compared with DIOP, due to better use of the delivery truck and a reduction of the number of dedicated inbound routes. Regarding OBP, fostering the use of OIRs does not necessarily lead to better routing plans than DIOP, as it depends upon a favourable geographical configuration of the set of customers to be visited in a day, specifically, the relative distance between a linehaul that can be visited last in a route, a neighboring backhaul, and a mill. The paper further provides valuable managerial insights on how the routing plan is impacted by the values of business-related model parameters which are set by the planner with some degree of uncertainty. Results suggest that increasing the maximum length of the route will likely have the largest impact in reducing transportation costs. Moreover, increasing the value of a reward paid for visiting a backhaul can foster the percentage of OIR in the optimal routing plan.     

高速铁路客运专线的收益管理模型

本文在分析铁路客运收益管理的研究进展的基础上,提出了一个适合铁路客运专线的收益管理优化模型。模型以列车运营总收益最大化为目标,优化列车的席位控制和发车间隔,将席位分配与运营能力优化统一在一个模型中。利用随机生成数据进行的模型试验表明,模型可以在较短的时间内求解较大规模的收益管理优化问题。     

A Simulated Annealing Approach to Communication Network Design

This paper explores the use of the meta-heuristic search algorithm Simulated Annealing for solving a minimum cost network synthesis problem. This problem is a common one in the design of telecommunication networks. The formulation we use models a number of practical problems with hop-limit, degree and capacity constraints. Emphasis is placed on a new approach that uses a knapsack polytope to select amongst a number of pre-computed traffic routes in order to synthesise the network. The advantage of this approach is that a subset of the best routes can be used instead of the whole set, thereby making the process of designing large networks practicable. Using simulated annealing, we solve moderately large networks (up to 30 nodes) efficiently.     

A practical model for last train rescheduling with train delay in urban railway transit networks

Last train timetable rescheduling aims at coordinating the arrival and departure times of feeder trains with connecting trains at transfer stations to eliminate the effect of unexpected incidents in train operations. It has become a challenging problem in the operations and management of urban railway transit networks because of high complexities in coordination among lines. In this paper, we propose a rescheduling model for last trains with the consideration of train delays caused by incidents that occurred in train operations. In the model, two aspects are considered. On one hand, we try to minimize the running time and the dwell time, and to maximize the average transfer redundant time and the network accessibility. On the other hand, we expect to minimize the difference between the original timetable and the rescheduled one. A genetic algorithm is developed to solve this problem. The case study of Beijing railway transit network shows that once a delay occurs in a section, the most effective way to adjust the timetable consists of adjusting the running time of trains that have strong transfer relationships with the delay section. If the delay is not substantially long, the suggested model would neutralize the influence of the delay.     

Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier

Flight retiming in airline scheduling consists in slightly modifying the scheduled departure time of some flights with the goal of providing a better service with a cheaper cost. In this research, the departure times must be selected from a small discrete set of options. The whole problem embeds flight retiming, fleet assignment, aircraft routing and crew pairing. Thus, the aim is to determine the departure times of the flights, the fleet assignment and the minimum cost aircraft and crew routes. The objective function takes into account a large cost associated with each crew member, a penalization for short or long connection times, a cost for crew members changing aircraft along their routes, and a minor penalty associated with the use of each aircraft. The constraints enforce aircraft maintenance and crew working rules. In this setting, flight retiming is allowed to potentially reduce the total costs and increase the robustness of the solution against delays by decreasing the number of aircraft changes.We propose and compare four heuristic algorithms based on a Mixed Integer Linear Programming model for the whole problem. The model contains path variables representing the crew pairings, and arc variables representing the aircraft routes. In the heuristic algorithms, column generation is applied on the path variables, and different flight retiming options are considered. The algorithms are tested on real-world instances of a regional carrier flying in the Canary Islands to evaluate their advantages and drawbacks. In particular, one of the algorithms, that uses the solution of the Linear Programming relaxation of the model to select promising options for the departure of the flights, turns out to be the most effective one. The obtained results show that costs can be significantly reduced through flight retiming while still keeping the computing times reasonably short. In addition, we perform a sensitivity analysis by including more retiming options and by using different aircraft and crew costs. Finally, we report the results on larger size instances obtained by combining real-world ones.     

Heuristic Procedures for Practical-Sized Uncapacitated Location-Capacitated Routing Problems*

Facility location and vehicle routing are two important logistical problems closely interrelated in many real-world applications where locating facilities and determining the associated multi-stop vehicle routes are required simultaneously. Previous research has found that using the classical facility location models on these location-routing problems (LRPs) may lead to suboptimal solutions. We propose an approximate approach for the LRPs, which first generates and improves feasible location/allocation schemes with the associated multi-stop routing costs approximated using some route length estimators. We then design the minimum-cost routes based on the location/allocation results. We review two estimators that can provide accurate approximations to the multi-stop route distances; define the uncapacitated location-capacitated routing problem; and evaluate several heuristic procedures for approximately solving the problem. Computational results show that when vehicle capacities are not too restrictive, the sequential procedures that incorporate the two robust route length estimators can produce good solutions to practical-sized problems with a reasonable amount of computational efforts.     

An Expected Consequence Approach to Route Choice in the Maritime Transportation of Crude Oil

Maritime transportation is the major conduit of international trade, and the primary link for global crude oil movement. Given the volume of oil transported on international maritime links, it is not surprising that oil spills of both minor and major types result, although most of the risk‐related work has been confined to the local settings. We propose an expected consequence approach for assessing oil‐spill risk from intercontinental transportation of crude oil that not only adheres to the safety guidelines specified by the International Maritime Organization but also outlines a novel technique that makes use of coarse global data to estimate accident probabilities. The proposed estimation technique, together with four of the most popular cost‐of‐spill models from the literature, were applied to study and analyze a realistic size problem instance. Numerical analyses showed that: a shorter route may not necessarily be less risky; an understanding of the inherent oil‐spill risk of different routes could potentially facilitate tanker routing decisions; and the associated negotiations over insurance premium between the transport company and the not‐for‐profit prevention and indemnity clubs. Finally, we note that only the linear model should be used with one of the three nonlinear cost‐of‐spill models for evaluating tanker routes.     

Location optimization of strategic alert sites for homeland defense

This research uses a location analysis approach for selecting aircraft alert sites for the defense of important national areas of interest identified by the US Department of Defense. Solutions are generated in a two step approach where the minimum number of sites is first identified using the location set covering problem and then the result is improved by finding the minimum aggregate network distance or p-median solution from the alternate optimal solutions to the LSCP. This approach also identifies the p-center solution to the problem ensuring equitable response to all areas of interest. Sensitivity analysis is performed to determine the impact of altering aircraft launch and flying times on the number of required alert sites and the amount of coverage provided by selecting fewer locations. Results indicate a significant increase in the number of alert locations needed in comparison to original military estimates. The research points out significant implications about future military base closure decisions and the trade-offs between cost and required response times of aircraft in a defense emergency.     

越库配送下考虑时空距离的库门分配与车辆调度优化

针对越库配送下考虑时空距离的库门分配与车辆路径问题,建立以车辆派遣成本、运输成本、时间惩罚成本、越库内部操作成本总和最小化为目标的库门分配与车辆路径优化模型。根据问题的特征设计改进的自适应遗传算法,并根据时空距离生成初始解。通过对不同规模的算例进行对比和分析,验证了模型的正确性和算法的有效性,结果表明,所得出的库门分配和车辆调度优化方案可以有效降低越库配送中心的运营成本。研究成果拓展和丰富了越库配送下的车辆路径问题研究,能为物流企业优化配送方案提供理论依据。     

WARRANTY COST ESTIMATION: A GOAL PROGRAMMING APPROACH

This paper proposes a goal programming approach to the warranty cost estimation problem. Past research on this topic has mostly dealt with a single objective—the minimization of the warranty reserve cost or the maximization of profit. A more realistic approach to warranty cost problems could, however, involve several goals, some of which might be conflicting to others. In this paper, three goals are prioritized. The goals considered are minimization of warranty reserve cost per unit, offering a minimum level of warranty time based on an allowable proportion of failures within the warranty period, and capturing a minimum specified market share of the product. An example is illustrated using the proposed formulation, and goal achievements are discussed.     

A Data‐Driven Inventory Control Policy for Cash Logistics Operations: An Exploratory Case Study Application at a Financial Institution

A number of market changes are impacting the way financial institutions are managing their automated teller machines (ATMs). We propose a new class of adaptive data‐driven policies for a stochastic inventory control problem faced by a large financial institution that manages cash at several ATMs. Senior management were concerned that their current cash supply system to manage ATMs was inefficient and outdated, and suspected that using improved cash management could reduce overall system cost. Our task was to provide a robust procedure to tackle the ATM's cash deployment strategies. Current industry practice uses a periodic review system with infrequent parameter updates for cash management based on the assumption that demand is normally distributed during the review period. This assumption did not hold during our investigation, warranting a new and robust analysis. Moreover, we discovered that forecast errors are often not normally distributed and that these error distributions change dramatically over time. Our approach finds the optimal time series forecaster and the best‐fitting weekly forecast error distribution. The guaranteed optimal target cash inventory level and time between orders could only be obtained through an optimization module that was embedded in a simulation routine that we built for the institution. We employed an exploratory case study methodology to collect cash withdrawal data at 21 ATMs owned and operated by the financial institution. Our new approach shows a 4.6% overall cost reduction. This reflects an annual cost savings of over $250,000 for the 2,500 ATM units that are operated by the bank.