带退货和软时间窗的多仓库选址-路径问题研究

选址-路径问题(location routing problems, LRP)是集成物流网络研究中的难题,也是任何一个大型物流配送企业必须面对的管理决策问题。本文在仓库容量约束和车辆容量约束的基础上,结合送取货一体化的配送模式和客户服务时间要求,建立了带退货和软时间窗的多仓库选址-路径(MDLRP)数学模型。针对MDLRP问题求解的复杂性,引入局部搜索算法和重组策略,设计了自适应混合遗传算法,对模型进行整体求解。最后进行数值实验,表明本文提出的模型和改进算法具有实用性和优越性,可为选址和车辆运输决策提供重要参考依据。     

A heuristic algorithm for the free newspaper delivery problem

This paper addresses the problem of finding an effective distribution plan to deliver free newspapers from a production plant to subway, bus, or tram stations. The overall goal is to combine two factors: first, the free newspaper producing company wants to minimize the number of vehicle trips needed to distribute all newspapers produced at the production plant. Second, the company is interested in minimizing the time needed to consume all newspapers, i.e., the time needed to get all the newspapers taken by the final readers. The resulting routing problem combines aspects of the vehicle routing problem with time windows, the inventory routing problem, and additional constraints related to the production schedule. We propose a formulation and different heuristic approaches, as well as a hybrid method. Computational tests with real world data show that the hybrid method is the best in various problem settings.     

The multi-trip vehicle routing problem

The basic vehicle routing problem is concerned with the design of a set of routes to serve a given number of customers, minimising the total distance travelled. In that problem, each vehicle is assumed to be used only once during a planning period, which is typically a day, and therefore is unrepresentative of many practical situations, where a vehicle makes several journeys during a day. The present authors have previously published an algorithm which outperformed an experienced load planner working on the complex, real-life problems of Burton's Biscuits, where vehicles make more than one trip each day. This present paper uses a simplified version of that general algorithm, in order to compare it with a recently published heuristic specially designed for the theoretical multi-trip vehicle routing problem.     

A network-consistent time-dependent travel time layer for routing optimization problems

In the vehicle routing literature, there is an increasing focus on time-dependent routing problems, where the time (or cost) to travel between any pair of nodes (customers, depots) depends on the departure time. The aim of such algorithms is to be able to take recurring congestion into account when planning logistics operations. To test algorithms for time-dependent routing problems, time-dependent problem data is necessary. This data usually comes in the form of three-dimensional travel time matrices that add the departure time as an extra dimension. However, most currently available time-dependent travel time matrices are not network-consistent, i.e., the travel times are not correlated both in time and in space. This stands in contrast to the behavior of real life congestion, which generally follows a specific pattern, appearing in specific areas and then affecting all travel times to and from those areas. As a result of the lack of available network-consistent travel time matrices, it is difficult to develop algorithms that are able to take this special structure of the travel time data into account.     

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.     

The pyramidal capacitated vehicle routing problem

This paper introduces the pyramidal capacitated vehicle routing problem (PCVRP) as a restricted version of the capacitated vehicle routing problem (CVRP). In the PCVRP each route is required to be pyramidal in a sense generalized from the pyramidal traveling salesman problem (PTSP). A pyramidal route is defined as a route on which the vehicle first visits customers in increasing order of customer index, and on the remaining part of the route visits customers in decreasing order of customer index.     

A co-evolutionary approach using information about future requests for dynamic vehicle routing problem with soft time windows

This paper presents a technique for integrating information about future customer requests to improve decision making for dynamic vehicle routing. We use a co-evolutionary approach to generate better waiting strategies such that the expected number of late-request customers who are served is maximized. An empirical evaluation of the proposed approach is performed within a previously reported hybrid genetic algorithm for the dynamic vehicle routing problem with time windows. Comparisons with other heuristic methods demonstrate the potential improvement that can be obtained through the application of the proposed approach.     

Solving a vehicle-routing problem arising in soft-drink distribution

The problem studied in this article arises from the distribution of soft drinks and collection of recyclable containers in a Quebec-based company. It can be modelled as a variant of the vehicle routing problem with a heterogeneous vehicle fleet, time windows, capacity and volume constraints, and an objective function combining routing costs and the revenue resulting from the sale of recyclable material. Three construction heuristics and an improvement procedure are developed for the problem. Comparative tests are performed on a real-life instance and on 10 randomly generated instances.     

Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model

In this paper, we address a variant of the vehicle routing problem called the vehicle routing problem with time windows and multiple routes. It considers that a given vehicle can be assigned to more than one route per planning period. We propose a new exact algorithm for this problem. Our algorithm is iterative and it relies on a pseudo-polynomial network flow model whose nodes represent time instants, and whose arcs represent feasible vehicle routes. This algorithm was tested on a set of benchmark instances from the literature. The computational results show that our method is able to solve more instances than the only other exact method described so far in the literature, and it clearly outperforms this method in terms of computing time.     

Disrupted capacitated vehicle routing problem with order release delay

With the popularity of the just-in-time system, more and more companies are operating with little or no inventories, which make them highly vulnerable to delays on supply. This paper discusses a situation when the supply of the commodity does not arrive at the depot on time, so that not enough of the commodity is available to be loaded on all vehicles at the start of the delivery period. New routing plans need to be developed in such a case to reduce the impact the delay of supply may have on the distribution company. The resulting vehicle routing problem is different from other types of vehicle routing problems as it involves waiting and multiple trips. Two approaches have been developed to solve the order release delay problem, both of which involve a Tabu Search algorithm. Computational results show the proposed approaches can largely reduce the disruption costs that are caused by the delayed supply and they are especially effective when the length of delay is long.     

Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts

We describe a solution procedure for a special case of the periodic vehicle routing problem (PVRP). Operation managers at an auto parts manufacturer in the north of Spain described the optimization problem to the authors. The manufacturer must pick up parts (raw material) from geographically dispersed locations. The parts are picked up periodically at scheduled times. The problem consists of assigning a pickup schedule to each of its supplier’s locations and also establishing daily routes in order to minimize total transportation costs. The time horizon under consideration may be as long as 90 days. The resulting PVRP is such that the critical decision is the assignment of locations to schedules, because once this is done, the daily routing of vehicles is relatively straightforward. Through extensive computational experiments, we show that the metaheuristic procedure described in this paper is capable of finding high-quality solutions within a reasonable amount of computer time. Our main contribution is the development of a procedure that is more effective at handling PVRP instances with long planning horizons when compared to those proposed in the literature.     

A robust optimization approach to dispatching technicians under stochastic service times

We consider the problem of dispatching technicians to service/repair geographically distributed equipment. This problem can be cast as a vehicle routing problem with time windows, where customers expect fast response and small delays. Estimates of the service time, however, can be subject to a significant amount of uncertainty due to misdiagnosis of the reason for failure or surprises during repair. It is therefore crucial to develop routes for the technicians that would be less sensitive to substantial deviations from estimated service times. In this paper we propose a robust optimization model for the vehicle routing problem with soft time windows and service time uncertainty and solve real-world instances with a branch and price method. We evaluate the efficiency of the approach through computational experiments on real industry routing data.     

A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries

The asymmetric vehicle routing problem with simultaneous pickup and deliveries is considered. This paper develops four new classes of valid inequalities for the problem. We generalize the idea of a no-good cut. Together, these help us solve 45-node randomly generated problem instances more efficiently. We report results on a set of benchmark instances in literature. In this set, we are able to show an order of magnitude improvement in computational times over currently published results in literature.     

Open vehicle routing problem with driver nodes and time deadlines

In this paper, we consider a variant of the open vehicle routing problem in which vehicles depart from the depot, visit a set of customers, and end their routes at special nodes called driver nodes. A driver node can be the home of the driver or a parking lot where the vehicle will stay overnight. The resulting problem is referred to as the open vehicle routing problem with driver nodes (OVRP-d). We consider three classes of OVRP-d: with no time constraints, with a maximum route duration, and with both a maximum route duration as well as time deadlines for visiting customers. For the solution of these problems, which are not addressed previously in the literature, we develop a new tabu search heuristic. Computational results on randomly generated instances indicate that the new heuristic exhibits a good performance both in terms of the solution quality and computation time.     

Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method

An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD) is considered. We propose a new heuristic method to solve the problem, based on the Cross-Entropy method. In order to better estimate the objective function at each point in the domain, we incorporate Monte Carlo sampling. This creates many practical issues, especially the decision as to when to draw new samples and how many samples to use. We also develop a framework for obtaining exact solutions and tight lower bounds for the problem under various conditions, which include specific families of demand distributions. This is used to assess the performance of the algorithm. Finally, numerical results are presented for various problem instances to illustrate the ideas.     

新能源移动充电车路径优化问题研究

在绿色城市背景下,新能源汽车的数量快速增长,现有公共充电设施的不完善使得移动充电服务应运而生。投入运营成本较高而利润低成为阻碍移动充电业务运营的瓶颈之一,如何通过科学合理的调度提高平台利润成为重要问题。本文研究了移动充电车队的调度和路径优化问题,以平台最大收益为目标,综合考虑顾客软时间窗、移动电池容量以及充电车续航里程等约束,建立数学规划模型;设计了一种最大最小蚁群算法,并通过数值实验验证了模型的合理性和算法的有效性,为移动充电企业运营提供决策参考。     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

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 unified tabu search heuristic for vehicle routing problems with time windows

This paper presents a unified tabu search heuristic for the vehicle routing problem with time windows and for two important generalizations: the periodic and the multi-depot vehicle routing problems with time windows. The major benefits of the approach are its speed, simplicity and flexibility. The performance of the heuristic is assessed by comparing it to alternative methods on benchmark instances of the vehicle routing problem with time windows. Computational experiments are also reported on new randomly generated instances for each of the two generalizations.     

A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem

The fleet size and mix vehicle routing problem consists of defining the type, the number of vehicles of each type, as well as the order in which to serve the customers with each vehicle when a company has to distribute goods to a set of customers geographically spread, with the objective of minimizing the total costs. In this paper, a heuristic algorithm based on tabu search is proposed and tested on several benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.