Multiscale production routing in multicommodity supply chains with complex production facilities

In this work, we introduce the multiscale production routing problem (MPRP), which considers the coordination of production, inventory, distribution, and routing decisions in multicommodity supply chains with complex continuous production facilities. We propose an MILP model involving two different time grids. While a detailed mode-based production scheduling model captures all critical operational constraints on the fine time grid, vehicle routing is considered in each time period of the coarse time grid. In order to solve large instances of the MPRP, we propose an iterative MILP-based heuristic approach that solves the MILP model with a restricted set of candidate routes at each iteration and dynamically updates the set of candidate routes for the next iteration. The results of an extensive computational study show that the proposed algorithm finds high-quality solutions in reasonable computation times, and in large instances, it significantly outperforms a standard two-phase heuristic approach and a solution strategy involving a one-time heuristic pre-generation of candidate routes. Similar results are achieved in an industrial case study, which considers a real-world industrial gas supply chain.     

A simulated annealing heuristic for the truck and trailer routing problem with time windows

European firms have been using a combination of trucks and trailers in the delivery/collection of food products for years. Thus, some previous studies had been devoted to improving the efficiency of the resulting truck and trailer routing problem (TTRP). Since time window constraints are present in many real-world routing applications, in this study, we introduce the truck and trailer routing problem with time windows (TTRPTW) to bring the TTRP model closer to the reality. A simulated annealing (SA) heuristic is proposed for solving the TTRPTW. Two computational experiments are conducted to test the performance of the proposed SA heuristic. The results indicate that the proposed SA heuristic is capable of consistently producing quality solutions to the TTRPTW within a reasonable time.     

A hybrid method based on linear programming and tabu search for routing of logging trucks

In this paper, we consider an operational routing problem to decide the daily routes of logging trucks in forestry. This industrial problem is difficult and includes aspects such as pickup and delivery with split pickups, multiple products, time windows, several time periods, multiple depots, driver changes and a heterogeneous truck fleet. In addition, the problem size is large and the solution time limited. We describe a two-phase solution approach which transforms the problem into a standard vehicle routing problem with time windows. In the first phase, we solve an LP problem in order to find a destination of flow from supply points to demand points. Based on this solution, we create transport nodes which each defines the origin(s) and destination for a full truckload. In phase two, we make use of a standard tabu search method to combine these transport nodes, which can be considered to be customers in vehicle routing problems, into actual routes. The tabu search method is extended to consider some new features. The solution approach is tested on a set of industrial cases from major forest companies in Sweden.     

A Simulation Based Restricted Dynamic Programming approach for the Green Time Dependent Vehicle Routing Problem

This paper addresses a Green Time Dependent Capacitated Vehicle Routing Problem that accounts for transportation emissions. The problem has been formulated and solved using Dynamic Programming approach. The applicability of Dynamic Programming in large sized problems is, however, limited due to exponential memory and computation time requirements. Therefore, we propose a generic heuristic approach, Simulation Based Restricted Dynamic Programming, based on weighted random sampling, the classical Restricted Dynamic Programming heuristic and simulation for the model to solve large sized instances. These decision support tools can be used to aid logistics decision-making processes in urban distribution planning. The added values of the proposed model and the heuristic have been shown based on a real life urban distribution planning problem between a pharmaceutical warehouse and a set of pharmacies, and ten relatively larger instances. The results of the numerical experiments show that the Simulation Based Restricted Dynamic Programming heuristic can provide promising results within relatively short computation times compared to the classical Restricted Dynamic Programming for the Green Time Dependent Capacitated Vehicle Routing Problem. The Simulation Based Restricted Dynamic Programming algorithm yields 2.3% lower costs within 93.1% shorter computation times on average, compared to the classical Restricted Dynamic Programming. Moreover, the analyses on the effect of traffic congestion in our base case reveal that 2.3% benefit on total emissions and 0.9% benefit on total routing cost could be obtained if vehicles start delivery after heavy congested period is passed.     

基于自适应蚁群算法的多受限网络QoS路由优化

高速多媒体网络中的路由问题是有QoS约束的路由问题，多受限的路由问题是一个NP-完全问题。该文提出了一种解决多受限QoS路由问题的自适应蚁群算法。该算法采用基于目标函数值的信息素分配策略和根据目标函数值自适应调整蚂蚁的搜索行为，从而保证搜索的快速有效性，使多受限QoS路由优化问题得到很好地解决。     

多跳多接口无线网络中的协作路由

协作通信可以利用空间分集效应抵抗无线信道衰弱而得到广泛关注。在多业务流多跳多接口无线协作网络中,研究联合路由选择和协作节点分配的最优化问题,将最大化最小业务流速率的联合优化问题建模为混合整数线性规划问题。针对这个问题提出一种基于分支定界的启发式算法JFRBB。JFRBB算法基于分支定界的思想是将原问题分解为多个子问题通过迭代获得最优解。仿真实验结果表明,JFRBB下的多接口协作网络获得的传输速率、聚合流量明显优于多接口无协作网络和单接口协作网络的性能。     

An effective heuristic for solving a combined cargo and inventory routing problem in tramp shipping

In this paper a vendor managed inventory (VMI) service in tramp shipping is considered. VMI takes advantage of introducing flexibility in delivery time and cargo quantities by transferring inventory management and ordering responsibilities to the vendor which in this case is a shipping company. A two-phase heuristic is proposed to determine routes and schedules for the shipping company. The heuristic first converts inventories into cargoes, thus turning the problem into a classic ship routing and scheduling problem. It then uses adaptive large neighborhood search to solve the resulting cargo routing and scheduling problem. The heuristic iteratively changes the cargoes generated to handle the customer’s inventories, based on the information obtained from an initial solution. Computational results are presented, discussed and compared with exact solutions on large realistic instances. The results reveal the potential savings from converting traditional contracts of affreightment to an integrated VMI service. The factors that influence the benefits obtainable through VMI are also analyzed.     

The two-echelon multi-trip vehicle routing problem with dynamic satellites for crop harvesting and transportation

The harvesting and transportation system involves a harvest scheduling and a transportation plan. The grain, harvested by combine-harvesters, is then transported by transporters from disperse farmlands to the depot. The spot where combine-harvesters transfer wheat to transporters is dynamic because the location of these spots correspond with combine-harvesters’ work. In this paper, the harvesting and transportation problem is considered as a two-echelon multi-trip vehicle routing problem with a dynamic satellite (2E-MTVRPDS) because the combine-harvester is used multiple times in the planning horizon and the transporter is used multiple times in a work day. The mixed integer linear programming model is proposed based on the features of the problem. This work presents an optimum solution with a heuristic algorithm. The dynamic satellite is transferred as the static case in the heuristic. The computational experiments are constructed to test the performances of the proposed algorithm. Five instances with different sizes are adopted to test the stability of the algorithm. The calculation deviation of testing instances is acceptable. On one hand, the optimal effectiveness can be achieved when the number of instances is less than 200. With the increase in the number of instances, the optimal efficiency declines. On the other hand, the optimal solution appears to have a time window of 0.2 h in all instances with different sizes. This study provides a decision model for agricultural production to implement optimal harvesting operations.     

The capacitated vehicle routing problem with stochastic demands and time windows

The capacitated vehicle routing problem with stochastic demands and time windows is an extension of the capacitated vehicle routing problem with stochastic demands, in which demands are stochastic and a time window is imposed on each vertex. A vertex failure occurring when the realized demand exceeds the vehicle capacity may trigger a chain reaction of failures on the remaining vertices in the same route, as a result of time windows. This paper models this problem as a stochastic program with recourse, and proposes an adaptive large neighborhood search heuristic for its solution. Modified Solomon benchmark instances are used in the experiments. Computational results clearly show the superiority of the proposed heuristic over an alternative solution approach.     

A simultaneous facility location,vehicle routing and dynamic pricing in a distribution network

This paper incorporates location, pricing and routing decisions by the goal of maximizing profit in a distribution network. In this problem, multiple consecutive time periods are considered in the decision of depot locations at the beginning of the planning horizon, pricing, and routing during each period. According to the varying willingness to pay (w.t.p) of the consumers across different regions and time periods, dynamic regional pricing techniques were incorporated into this problem. In this study, a non-linear mixed integer model is proposed for solving the problem. This model is then converted into a mixed integer quadratic constrained problem that can be solved with the CPLEX solver. Due to the inability of the exact algorithm to solve certain medium and all large instances, and in order to improve the obtained upper bounds for medium test problems, lagrangian relaxation (LR) was introduced. Two pure and hybrid heuristic algorithms are proposed for tackling this problem. The heuristic algorithm includes price optimization and location-routing steps. In the hybrid heuristics, these steps are embedded in the particle swarm optimization (PSO) and self-learning PSO (SLPSO) algorithms framework. Computational experiments illustrate the efficiency of the proposed algorithms. Sensitivity analysis indicates the necessity of switching from the pure heuristic to the hybrid version for scarce capacity settings.     

The inventory-routing problem with transshipment

This paper introduces the Inventory-Routing Problem with Transshipment (IRPT). This problem arises when vehicle routing and inventory decisions must be made simultaneously, which is typically the case in vendor-managed inventory systems. Heuristics and exact algorithms have already been proposed for the Inventory-Routing Problem (IRP), but these algorithms ignore the possibility of performing transshipments between customers so as to further reduce the overall cost. We present a formulation that allows transshipments, either from the supplier to customers or between customers. We also propose an adaptive large neighborhood search heuristic to solve the problem. This heuristic manipulates vehicle routes while the remaining problem of determining delivery quantities and transshipment moves is solved through a network flow algorithm. Our approach can solve four different variants of the problem: the IRP and the IRPT, under maximum level and order-up-to level policies. We perform an extensive assessment of the performance of our heuristic.     

带度约束的最小直径应用层多播路由问题的启发式遗传算法

由于IP多播难以在因特网环境中配置,应用层多播作为IP多播的一种替代方案得到越来越多的研究。从网络设计的角度来看,应用层多播在网络代价模型及路由策略方面与传统的IP多播有很大区别。本文研究了带度约束的最小直径应用层网络多播路由问题,提出了解决该问题的启发式遗传算法。通过大量仿真实验,我们对比分析了两种贪婪算法法和遗传算法的性能。实验显示,启发式遗传算法具有较好的性能。     

Direct shipping logistic planning for a hub-and-spoke network with given discrete intershipment times

This paper proposes a heuristic procedure to solve the problem of scheduling and routing shipments in a hybrid hub‐and‐spoke network, when a given set of feasible discrete intershipment times is given. The heuristic procedure may be used to assist in the cooperative operational planning of a physical goods network between shippers and logistics service provider, or to assist shippers in making logistics outsourcing decisions. The objective is to minimise the transportation and inventory holding costs. It is shown through a set of problem instances that this heuristic procedure provides better solutions than existing economic order quantity‐based approaches. Computational results are presented and discussed.     

A Multi-Trip Split-Delivery Vehicle Routing Problem with Time Windows for Inventory Replenishment Under Stochastic Travel Times

This study considers a multi-trip split-delivery vehicle routing problem with soft time windows for daily inventory replenishment under stochastic travel times. Considering uncertainty in travel times for vehicle routing problems is beneficial because more robust schedules can be generated and unanticipated consequences can be reduced when schedules are implemented in reality. However, uncertainties in model parameters have rarely been addressed for the problems in this category mainly due to the high problem complexity. In this study, an innovative and practical approach is proposed to consider stochastic travel times in the planning process. In the planning model, the possible outcomes of vehicle arrivals and product delivery at retailers are systematically categorized and their associated penalty and reward are estimated. Thus, unanticipated costs for every scheduling decision can be incorporated into the planning model to generate vehicle routing schedules that are more robust facing uncertain traffic conditions. To solve the model that is characterized as an NP-hard problem in a reasonable amount of time, a two-stage heuristic solution algorithm is proposed. Finally, the stochastic model is compared with the deterministic model in both planning and simulated operation stages using the data of a supply chain in Taiwan. The result confirms that the schedule generated by the stochastic model is more robust than the one created with the deterministic model because undesired outcomes such as unfulfilled demands are greatly reduced.     

Battery swap station location-routing problem with capacitated electric vehicles

In this paper, we present an electric vehicles battery swap stations location routing problem (BSS–EV–LRP), which aims to determine the location strategy of battery swap stations (BSSs) and the routing plan of a fleet of electric vehicles (EVs) simultaneously under battery driving range limitation. The problem is formulated as an integer programming model under the basic and extended scenarios. A four-phase heuristic called SIGALNS and a two-phase Tabu Search-modified Clarke and Wright Savings heuristic (TS-MCWS) are proposed to solve the problem. In the proposed SIGALNS, the BSSs location stage and the vehicle routing stage are alternated iteratively, which considers the information from the routing plan while improving the location strategy. In the first phase, an initial routing plan is generated with a modified sweep algorithm, leading to the BSSs location subproblem, which is then solved by using an iterated greedy heuristic. In the third phase, the vehicle routes resulting from the location subproblem are determined by applying an adaptive large neighborhood search heuristic with several new neighborhood structures. At the end of SIGALNS, the solution is further improved by a split procedure. Compared with the MIP solver of CPLEX and TS-MCWS over three sets of instances, SIGALNS searches the solution space more efficiently, thus producing good solutions without excessive computation on the medium and large instances. Furthermore, we systematically conduct economic and environmental analysis including the comparison between basic and extended scenarios, sensitivity analysis on battery driving range and efficiency analysis about the vehicle emissions reduction when EVs are used in the logistics practice.     

A linear programming-based method for job shop scheduling

We present a decomposition heuristic for a large class of job shop scheduling problems. This heuristic utilizes information from the linear programming formulation of the associated optimal timing problem to solve subproblems, can be used for any objective function whose associated optimal timing problem can be expressed as a linear program (LP), and is particularly effective for objectives that include a component that is a function of individual operation completion times. Using the proposed heuristic framework, we address job shop scheduling problems with a variety of objectives where intermediate holding costs need to be explicitly considered. In computational testing, we demonstrate the performance of our proposed solution approach.     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

VARIABLE PATROL PLANNING OF MULTI-ROBOT SYSTEMS BY A COOPERATIVE AUCTION SYSTEM

A cooperative auction system (CAS) is proposed to solve the large-scale multi-robot patrol planning problem. Each robot picks its own patrol points via the cooperative auction system and the system continuously re-auctions, based on the team work performance. The proposed method not only works in static environments but also considers variable path planning when the number of mobile robots increases or decreases during patrol. From the results of the simulation, the proposed approach demonstrates decreased time complexity, a lower routing path cost, improved balance of workload among robots, and the potential to scale to a large number of robots and is adaptive to environmental perturbations when the number of robots changes during patrol.     

A note on the truck and trailer routing problem

This study considers the relaxed truck and trailer routing problem (RTTRP), a relaxation of the truck and trailer routing problem (TTRP). TTRP is a variant of the well studied vehicle routing problem (VRP). In TTRP, a fleet of trucks and trailers are used to service a set of customers with known demands. Some customers may be serviced by a truck pulling a trailer, while the others may only be serviced by a single truck. This is the main difference between TTRP and VRP. The number of available trucks and available trailers is limited in the original TTRP but there are no fixed costs associated with the use of trucks or trailers. Therefore, it is reasonable to relax this fleet size constraint to see if it is possible to further reduce the total routing cost (distance). In addition, the resulting RTTRP can also be used to determine a better fleet mix. We developed a simulated annealing heuristic for solving RTTRP and tested it on 21 existing TTRP benchmark problems and 36 newly generated TTRP instances. Computational results indicate that the solutions for RTTRP are generally better than the best solutions in the literature for TTRP. The proposed SA heuristic is able to find better solutions to 18 of the 21 existing benchmark TTRP instances. The solutions for the remaining three problems are tied with the best so far solutions in the literature. For the 36 newly generated problems, the average percentage improvement of RTTRP solutions over TTRP solutions is about 5%. Considering the ever rising crude oil price, even small reduction in the route length is significant.     

Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks

Sensors are tiny electronic devices having limited battery energy and capability for sensing, data processing and communicating. They can collectively behave to provide an effective wireless network that monitors a region and transmits the collected information to gateway nodes called sinks. Most of the applications require the operation of the network for long periods of times, which makes the efficient management of the available energy resources an important concern. There are three major issues in the design of sensor networks: sensor deployment or the coverage of the sensing area, sink location, and data routing. In this work, we consider these three design problems within a unified framework and develop two mixed-integer linear programming formulations. They are difficult to solve exactly. However, it is possible to compute good feasible solutions of the sink location and routing problems easily, when the sensors are deployed and their locations in the sensor field become known. Therefore, we propose a tabu search heuristic that tries to identify the best sensor locations satisfying the coverage requirements. The objective value corresponding to each set of sensor locations is calculated by solving the sink location and routing problem. Computational tests carried out on randomly generated test instances indicate that the proposed hybrid approach is both accurate and efficient.