A multi-objective mathematical model for the industrial hazardous waste location-routing problem

Industrial hazardous waste management involves the collection, transportation, treatment, recycling and disposal of industrial hazardous materials that pose risk to their surroundings. In this paper, a new multi-objective location-routing model is developed, and implemented in the Marmara region of Turkey. The aim of the model is to help decision makers decide on locations of treatment centers utilizing different technologies, routing different types of industrial hazardous wastes to compatible treatment centers, locations of recycling centers and routing hazardous waste and waste residues to those centers, and locations of disposal centers and routing waste residues there. In the mathematical model, three criteria are considered: minimizing total cost, which includes total transportation cost of hazardous materials and waste residues and fixed cost of establishing treatment, disposal and recycling centers; minimizing total transportation risk related to the population exposure along transportation routes of hazardous materials and waste residues; and minimizing total risk for the population around treatment and disposal centers, also called site risk. A lexicographic weighted Tchebycheff formulation is developed and computed with CPLEX software to find representative efficient solutions to the problem. Data related to the Marmara region is obtained by utilizing Arcview 9.3 GIS software and Marmara region geographical database.     

A multilevel machine and vehicle scheduling in a flexible manufacturing system

The paper presents a multilevel decision model for simultaneous machine and vehicle scheduling in a flexible manufacturing system. The system is composed of various machine types and a set of automated guided vehicles that permit each part to move between any pair of machines. The upper level of the decision model involves machine loading and part routing for which a bicriterion integer formulation is presented with the objective of balancing machine workloads and intermachine flows of parts. The lower level involves simultaneous scheduling of machines and vehicles for which a period-by-period heuristic is proposed based on a family of complex dispatching rules. The scheduling objective is to meet all part type requirements in a minimum time. Computational examples are included to illustrate the approach proposed.     

A heuristic method for the open vehicle routing problem

The open vehicle routing problem (OVRP) differs from the classic vehicle routing problem (VRP) because the vehicles either are not required to return to the depot, or they have to return by revisiting the customers assigned to them in the reverse order. Therefore, the vehicle routes are not closed paths but open ones. A heuristic method for solving this new problem, based on a minimum spanning tree with penalties procedure, is presented. Computational results are provided.     

成品油配送多车舱车辆指派及路径优化问题研究

针对成品油配送中多车型、多车舱的车辆优化调度难题,综合考虑多车型车辆指派、多车舱车辆装载及路径安排等决策,以派车成本与油耗成本之和的总成本最小为目标,建立了多车型多车舱的车辆优化调度模型。为降低模型求解的复杂性,本文提出一种基于C-W节约算法的“需求拆分→合并装载”的车辆装载策略,并综合利用Relocate和Exchange算子进行并行邻域搜索改进,获得优化的成品油配送方案。最后,通过算例验证了本文提出的模型与算法用于求解大规模成品油配送问题的有效性。并通过数据实验揭示了以下规律:1)多车舱车辆相对于单车舱车辆在运营成本上具有优越性;2)大型车辆适合远距离配送,小型车辆适合近距离配送;3)多车型车辆混合配送相对于单车型车辆配送在运营成本上具有优越性。这些规律可为成品油配送公司的车辆配置提供决策参考。     

A worst-case analysis for the split delivery vehicle routing problem with minimum delivery amounts

In the vehicle routing problem (VRP), a fleet of vehicles must service the demands of customers in a least-cost way. In the split delivery vehicle routing problem (SDVRP), multiple vehicles can service the same customer by splitting the deliveries. By allowing split deliveries, savings in travel costs of up to 50 % are possible, and this bound is tight. Recently, a variant of the SDVRP, the split delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA), has been introduced. In the SDVRP-MDA, split deliveries are allowed only if at least a minimum fraction of a customer’s demand is delivered by each visiting vehicle. We perform a worst-case analysis on the SDVRP-MDA to determine tight bounds on the maximum possible savings.     

An adaptive routing approach for personal rapid transit

Personal Rapid Transit (PRT) is a public transportation mode, in which small automated vehicles transport passengers on demand. Central control of the vehicles leads to interesting possibilities for optimized routings. The complexity of the involved routing problems together with the fact that routing algorithms for PRT essentially have to run in real-time often leads to the choice of fast greedy approaches. The most common routing approach is arguably a sequential one, where upcoming requests are greedily served in a quickest way without interfering with previously routed vehicles. The simplicity of this approach stems from the fact that a chosen route is never changed later. This is as well the main drawback of it, potentially leading to large detours. It is natural to ask how much one could gain by using a more adaptive routing strategy. This question is the main motivation of this article. In this paper, we first suggest a simple mathematical model for PRT, and then introduce a new adaptive routing algorithm that repeatedly uses solutions to an LP as a guide to route vehicles. Our routing approach incorporates new requests in the LP as soon as they appear, and reoptimizes the routing of all currently used vehicles, contrary to sequential routing. We provide preliminary computational results that give first evidence of the potential gains of an adaptive routing strategy, as used in our algorithm.     

Finished-vehicle transporter routing problem solved by loading pattern discovery

This work addresses a new transportation problem in outbound logistics in the automobile industry: the finished-vehicle transporter routing problem (FVTRP). The FVTRP is a practical routing problem with loading constraints, and it assumes that dealers have deterministic demands for finished vehicles that have three-dimensional irregular shapes. The problem solution will identify optimal routes while satisfying demands. In terms of complex packing, finished vehicles are not directly loaded into the spaces of transporters; instead, loading patterns matching finished vehicles with transporters are identified first by mining successful loading records through virtual and manual loading test procedures, such that the packing problem is practically solved with the help of a procedure to discover loading patterns. This work proposes a mixed-integer linear programming (MILP) model for the FVTRP considering loading patterns. As a special class of routing models, the FVTRP is typically difficult to solve within a manageable computing time. Thus, an evolutionary algorithm is designed to solve the FVTRP. Comparisons of the proposed algorithm and a commercial MILP solver demonstrate that the proposed algorithm is more effective in solving medium- and large-scale problems. The proposed scheme for addressing the FVTRP is illustrated with an example and tested with benchmark instances that are derived from well-studied vehicle routing datasets.     

Dynamic system optimal performances of shared autonomous and human vehicle system for heterogeneous travellers

ABSTRACT

Autonomous vehicles (AV) can solve vehicle relocation problems faced by traditional one-way vehicle-sharing systems. This paper explores the deterministic time-dependent system optimum of mixed shared AVs (SAV) and human vehicles (SHV) system to provide the benchmark for the situation of mixed vehicle flows. In such a system, the system planner determines vehicle-traveller assignment and optimal vehicle routing in transportation networks to serve predetermined travel demand of heterogeneous travellers. Due to large number of vehicles involved, travel time is considered endogenous with congestion. Using link transmission model (LTM) as a traffic flow model, the deterministic time-dependent system optimum is formulated as linear programming (LP) model to minimize the comprehensive cost including travellers’ travel time cost, waiting time cost and empty vehicle repositioning time cost. Numerical examples are conducted to show system performances and model effectiveness.     

Metaheuristics for vehicle routing problems with three-dimensional loading constraints

This paper addresses an important combination of three-dimensional loading and vehicle routing, known as the Three-Dimensional Loading Capacitated Vehicle Routing Problem. The problem calls for the combined optimization of the loading of freight into vehicles and the routing of vehicles along a road network, with the aim of serving customers with minimum traveling cost. Despite its clear practical relevance in freight distribution, the literature on this problem is very limited. This is because of its high combinatorial complexity.     

A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems

This paper considers a transportation problem for moving empty or laden containers for a logistic company. Owing to the limited resource of its vehicles (trucks and trailers), the company often needs to sub-contract certain job orders to outsourced companies. A model for this truck and trailer vehicle routing problem (TTVRP) is first constructed in the paper. The solution to the TTVRP consists of finding a complete routing schedule for serving the jobs with minimum routing distance and number of trucks, subject to a number of constraints such as time windows and availability of trailers. To solve such a multi-objective and multi-modal combinatorial optimization problem, a hybrid multi-objective evolutionary algorithm (HMOEA) featured with specialized genetic operators, variable-length representation and local search heuristic is applied to find the Pareto optimal routing solutions for the TTVRP. Detailed analysis is performed to extract useful decision-making information from the multi-objective optimization results as well as to examine the correlations among different variables, such as the number of trucks and trailers, the trailer exchange points, and the utilization of trucks in the routing solutions. It has been shown that the HMOEA is effective in solving multi-objective combinatorial optimization problems, such as finding useful trade-off solutions for the TTVRP routing problem.     

A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions

In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented.     

A portfolio theory approach to crop planning under environmental constraints

This paper presents a multiobjective model for crop planning in agriculture. The approach is based on portfolio theory. The model takes into account weather risks, market risks and environmental risks. Input data include historical land productivity data for various crops, soil types and yield response to fertilizer/pesticide application. Several environmental levels for the application of fertilizers/pesticides, and the monetary penalties for overcoming these levels, are also considered. Starting from the multiobjective model we formulate several single objective optimization problems: the minimum environmental risk problem, the maximum expected return problem and the minimum financial risk problem. We prove that the minimum environmental risk problem is equivalent to a mixed integer problem with a linear objective function. Two numerical results for the minimum environmental risk problem are presented.     

Integer linear programming models for a cement delivery problem

We consider a cement delivery problem with an heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the capacity of the vehicles which means that most customers are visited several times. This is a split delivery vehicle routing problem with additional constraints. We first propose a two phase solution method that assigns deliveries to the vehicles, and then builds vehicle routes. Both subproblems are formulated as integer linear programming problems. We then show how to combine the two phases in a single integer linear program. Experiments on real life instances are performed to compare the performance of the two solution methods.     

Selective and periodic inventory routing problem for waste vegetable oil collection

We consider a biodiesel production company that collects waste vegetable oil from source points that generate waste in large amounts. The company uses the collected waste as raw material for biodiesel production. The manager of this company needs to decide which of the present source points to include in the collection program, which of them to visit on each day, which periodic routing schedule to repeat over an infinite horizon and how many vehicles to operate such that the total collection, inventory and purchasing costs are minimized while the production requirements and operational constraints are met. For this selective and periodic inventory routing problem, we propose two different formulations, compare them and apply the better performing one on a real-world problem with 36 scenarios. We generate lower bounds using a partial linear relaxation model, and observe that the solutions obtained through our model are within 3.28% of optimality on the average. Several insights regarding the customer selection, routing and purchasing decisions are acquired with sensitivity analysis.     

Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation

This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.     

突发事件应急医疗物资调度的随机算法

传统的车辆路径问题(VRP)是为车辆设计将物资从仓库运送到各个需求客户的路线,使得总的运输费用(或时间)最小。在本文中,我们更关心的是使得未满足的需求量和总的物资延误时间最小。这个模型的一个非常重要的应用就是当大规模突发事件发生以后如何有效的将应急医疗物资运送到各个医疗单位,例如自然灾难,恐怖袭击之后,各个医院的医疗物资有限,需要从应急中心调集所需物资,在这种情况下,从应急中心分发应急物资过程中的运输费用就不再是最主要的考查因素,而更重要的是考虑物资到达医院的时间以及到达量,因为这两个因素直接与病人生命息息相关。本文的主要工作是改进了已有的局部搜索算法,通过引入随机算法的思想设计了求解模型的改进随机算法,可以得到模型更优的解,并通过计算机模拟案例说明了算法是行之有效的。     

A new mixed integer linear model for a rich vehicle routing problem with docking constraints

In this paper we address a rich vehicle routing problem that arises in real-life applications. Among other aspects we consider time windows, simultaneous delivery and pick-up at customer locations and multiple use of vehicles. To guarantee a coordinated material flow at the depot, we include the timed allocation of vehicles to loading bays at which the loading and unloading activities can occur. The resulting vehicle routing problem is formulated as a two-index vehicle-flow model which integrates the routing under real-life conditions and the assignment of vehicles to loading bays at the depot. We use CPLEX 11.0 to solve medium-sized instances that are derived from the extended Solomon test set. The selective implementation of preprocessing techniques and cutting planes improves the solver performance significantly.     

Emergency Logistics Planning in Natural Disasters

Logistics planning in emergency situations involves dispatching commodities (e.g., medical materials and personnel, specialised rescue equipment and rescue teams, food, etc.) to distribution centres in affected areas as soon as possible so that relief operations are accelerated. In this study, a planning model that is to be integrated into a natural disaster logistics Decision Support System is developed. The model addresses the dynamic time-dependent transportation problem that needs to be solved repetitively at given time intervals during ongoing aid delivery. The model regenerates plans incorporating new requests for aid materials, new supplies and transportation means that become available during the current planning time horizon. The plan indicates the optimal mixed pick up and delivery schedules for vehicles within the considered planning time horizon as well as the optimal quantities and types of loads picked up and delivered on these routes. In emergency logistics context, supply is available in limited quantities at the current time period and on specified future dates. Commodity demand is known with certainty at the current date, but can be forecasted for future dates. Unlike commercial environments, vehicles do not have to return to depots, because the next time the plan is re-generated, a node receiving commodities may become a depot or a former depot may have no supplies at all. As a result, there are no closed loop tours, and vehicles wait at their last stop until they receive the next order from the logistics coordination centre. Hence, dispatch orders for vehicles consist of sets of “broken” routes that are generated in response to time-dependent supply/demand. The mathematical model describes a setting that is considerably different than the conventional vehicle routing problem. In fact, the problem is a hybrid that integrates the multi-commodity network flow problem and the vehicle routing problem. In this setting, vehicles are also treated as commodities. The model is readily decomposed into two multi-commodity network flow problems, the first one being linear (for conventional commodities) and the second integer (for vehicle flows). In the solution approach, these sub-models are coupled with relaxed arc capacity constraints using Lagrangean relaxation. The convergence of the proposed algorithm is tested on small test instances as well as on an earthquake scenario of realistic size.     

Towards a decision support system for the ready concrete distribution system: A case of a Greek company

The aim of this paper is to present an approach to the design of a Decision Support System for the dynamic routing of the various types of vehicles that are necessary for the daily distribution of the ready concrete product. This paper consists of two parts: in the first part the problem is analytically presented, thus setting the basics for building the problem’s model. At the same time special focus has been devoted in analyzing the corresponding parameters. In the second part the effort is to determine the information needed and the information available with respect to the techniques and the methods that are used in the optimization process. In addition, the workflow of the routing and scheduling procedures are presented. This is followed by the presentation of a prototype Decision Support System.     

Integer programming formulations of vehicle routing problems

Various mathematical formulations are available for situations represented by vehicle routing problems. The assignment-based integer programming formulations of these problems are more common and easy to understand. Such formulations are discussed in this paper and a much simpler formulation for the vechicle routing problem is presented for the case, when all the vehicles have the same load capacity and maximum allowable cost per route.