An exact algorithm for vehicle routing and scheduling problem of free pickup and delivery service in flight ticket sales companies based on set-partitioning model

This paper addresses a vehicle routing and scheduling problem arising in Flight Ticket Sales Companies for the service of free pickup and delivery of airline passengers to the airport. The problem is formulated under the framework of Vehicle Routing Problem with Time Windows (VRPTW), with the objective of minimizing the total operational costs, i.e. fixed start-up costs and variable traveling costs. A 0?C1 mixed integer programming model is presented, in which service quality is factored in constraints by introducing passenger satisfaction degree functions that limit time deviations between actual and desired delivery times. The problem addressed in this paper has two distinctive characteristics??small vehicle capacities and tight delivery time windows. An exact algorithm based on the set-partitioning model, concerning both characteristics, is developed. In the first phase of the algorithm the entire candidate set of best feasible routes is generated, and then the optimal solution is obtained by solving the set-partitioning model in the second phase. Finally, we use four actual instances to illustrate application of the proposed algorithm. Moreover, the proposed algorithm is applied to a random instance containing more orders to verify the general effectiveness of the proposed algorithm even if the number of passengers increases in future.     

基于遗传算法的集送一体化的车辆路径问题

有时间窗的集送货一体化的车辆路径问题(VRPPDTW)是对经典的车辆路径问题(VRP)的扩展,是一类重要的组合优化问题,但是目前对该问题的研究非常有限。论文采用了新的染色体编码方法,设计了遗传算法对该问题进行求解。在求解过程中,对集送一体化、多种配送车辆类型的问题进行了有效处理,同时考虑了车辆载重量和时间窗等约束。最后的实验结果表明,该算法可以求得这类车辆路径问题的最优解或次优解。     

An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen

The vehicle routing problem with time windows and multiple deliverymen (VRPTWMD) is a variant of the vehicle routing problem with time windows in which service times at customers depend on the number of deliverymen assigned to the route that serves them. In particular, a larger number of deliverymen in a route leads to shorter service times. Hence, in addition to the usual routing and scheduling decisions, the crew size for each route is also an endogenous decision. This problem is commonly faced by companies that deliver goods to customers located in busy urban areas, a situation that requires nearby customers to be grouped in advance so that the deliverymen can serve all customers in a group during one vehicle stop. Consequently, service times can be relatively long compared to travel times, which complicates serving all scheduled customers during regular work hours. In this paper, we propose a hybrid method for the VRPTWMD, combining a branch-price-and-cut (BPC) algorithm with two metaheuristic approaches. We present a wide variety of computational results showing that the proposed hybrid approach outperforms the BPC algorithm used as standalone method in terms of both solution quality and running time, in some classes of problem instances from the literature. These results indicate the advantages of using specific algorithms to generate good feasible solutions within an exact method.     

A dynamic vehicle routing problem with time-dependent travel times

In this paper we present a formulation for the dynamic vehicle routing problem with time-dependent travel times. We also present a genetic algorithm to solve the problem. The problem is a pick-up or delivery vehicle routing problem with soft time windows in which we consider multiple vehicles with different capacities, real-time service requests, and real-time variations in travel times between demand nodes.The performance of the genetic algorithm is evaluated by comparing its results with exact solutions and lower bounds for randomly generated test problems. For small size problems with up to 10 demands, the genetic algorithm provides almost the same results as the exact solutions, while its computation time is less than 10% of the time required to produce the exact solutions. For the problems with 30 demand nodes, the genetic algorithm results have less than 8% gap with lower bounds.This research also shows that as the uncertainty in the travel time information increases, a dynamic routing strategy that takes the real-time traffic information into account becomes increasingly superior to a static one. This is clear when we compare the static and dynamic routing strategies in problem scenarios that have different levels of uncertainty in travel time information. In additional tests on a simulated network, the proposed algorithm works well in dealing with situations in which accidents cause significant congestion in some part of the transportation network.     

Multicriteria pickup and delivery problem with transfer opportunity

In this research, we develop a multiobjective vehicle routing and scheduling heuristic for a pickup and delivery problem. The problem contains time window, advanced request, multi-vehicle and many-to-many transport. In addition, the fleet size is not predetermined, and customers are allowed to transfer between vehicles. The objectives of scheduling are to minimize vehicle expense, tardiness and travel time. We propose a concurrent scheduling approach, which allocates customers to more than one vehicle and assigns more than one customer to a vehicle at a time. It differs from the usual concurrent approach in three aspects: (i) it uses the look-ahead strategy to construct miniroute; (ii) it adopts the head/tail, head, and tail integration techniques; and (iii) it allows interactivity. The procedure takes full advantage of due time and travel time information and is implemented through a computer program. It is a one-phase heuristic that can be reiterated when necessary. We provide detailed programming procedures and present the computational results of the proposed algorithm through the real data.     

A branch-and-price-and-check model for the vehicle routing problem with location congestion

This paper considers a vehicle routing problem with pickup and delivery, time windows and location congestion. Locations provide a number of cumulative resources that are utilized by vehicles either during service (e.g., forklifts) or for the entirety of their visit (e.g., parking bays). Locations can become congested if insufficient resources are available, upon which vehicles must wait until a resource becomes available before proceeding. The problem is challenging from a computational standpoint since it incorporates the vehicle routing problem and the resource-constrained project scheduling problem. The main contribution of this paper is a branch-and-price-and-check model that uses a branch-and-price algorithm that solves the underlying vehicle routing problem, and a constraint programming subproblem that checks the feasibility of the location resource constraints, and then adds combinatorial nogood cuts to the master problem if the resource constraints are violated. Experimental results show the benefits of the branch-and-price-and-check approach.     

An arc flow formulation to the multitrip production,inventory, distribution,and routing problem with time windows

The multitrip production, inventory, distribution, and routing problem with time windows (MPIDRPTW) is an integrated problem that combines a production and distribution problem, a multitrip vehicle routing problem, and an inventory routing problem. In the MPIDRPTW, a set of customers, which have a time-varying demand during a finite planning horizon, is served by a single production facility. The distribution is accomplished by a fleet of homogeneous vehicles that deliver the customer orders within their specific time windows. Production management has to be done according to the inventories at the facility and at the customers. An exact arc flow model based on a graph is proposed to solve the MPIDRPTW, where the nodes represent instants of time. The main goal of the problem is to minimize the costs associated with the entire system. The proposed approach was implemented and a set of experimental tests were conducted based on a set of adapted instances from the literature.     

A variable neighborhood search heuristic algorithm for the double vehicle routing problem with multiple stacks

This paper addresses the double vehicle routing problem with multiple stacks (DVRPMS) in which a fleet of vehicles must collect items in a pickup region and then travel to a delivery region where all items are delivered. The load compartment of all vehicles is divided into rows (horizontal stacks) of fixed profundity (horizontal heights), and on each row, the unloading process must respect the last‐in‐first‐out policy. The objective of the DVRPMS is to find optimal routes visiting all pickup and delivery points while ensuring the feasibility of the vehicle loading plans. We propose a new integer linear programming formulation, which was useful to find inconsistencies in the results of exact algorithms proposed in the literature, and a variable neighborhood search based algorithm that was able to find solutions with same or higher quality in shorter computational time for most instances when compared to the methods already present in the literature.     

Vehicle routing and scheduling with dynamic travel times

The field of dynamic vehicle routing and scheduling is growing at a fast pace nowadays, due to many potential applications in courier services, emergency services, truckload and less-than-truckload trucking, and many others. In this paper, a dynamic vehicle routing and scheduling problem with time windows is described where both real-time customer requests and dynamic travel times are considered. Different reactive dispatching strategies are defined and compared through the setting of a single “tolerance” parameter. The results show that some tolerance to deviations with the current planned solution usually leads to better solutions.     

有软时窗约束带取送作业的车辆路径问题及其禁忌搜索算法研究

有软时窗约束带取送作业的车辆路径问题是在基本的车辆路径问题上增加了取送作业和时间窗约束的一种变化形式,是一个典型的NP-难问题.本文建立了问题模型,运用改进的禁忌搜索算法测试了根据实际状况构造的一个大规模算例.快速获得的高质量解验证了模型的正确性和算法性能的优良性.     

求解复杂有时间窗装卸货问题的遗传算法

有时间窗装卸货问题是为一个车队安排最优的服务路径以满足客户的运输需求,每个客户的装卸货任务由一辆车完成,即在该客户的装货点装载一定数量的货物后运往该客户的卸货点,所有任务的完成必须满足车辆的容量约束、行程约束和客户装卸货点的时间窗约束。从多车库、多货物类型和满载三个方面对一般有时间窗装卸问题（PDPTW）进行了扩展,提出一种解决复杂PDPTW问题的遗传算法,实验结果表明,该算法能有效解决复杂PDPTW问题,并取得较好的优化结果。     

A planning model and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows

This study proposes a daily vehicle routing model for minimizing the total cost of replenishing inventory within a supply chain. The first major contribution of this research is to allow multiple use of vehicles in a split delivery vehicle routing problem with time windows (SDVRPTW), which is more realistic for various real-life applications. The multi-trip SDVRPTW (MTSDVRPTW) is formulated using the time–space network technique, which provides greater flexibility for formulating the complicated interactions between vehicles and products when multi-trip, split delivery, and delivery time windows are simultaneously considered. The resulting formulation of the MTSDVRPTW can be categorized as an integer multi-commodity network flow problem with side constraints. A two-step solution algorithm is proposed to solve this NP-hard problem, which is the second major contribution of this research. Finally, a real-world scale numerical example is performed to demonstrate and to test the methodology. The results indicate that these vehicle routing problems can be solved effectively and efficiently and that the proposed methodology has great potential for inventory replenishment scheduling where split deliveries and multiple trips for a single vehicle are allowed and time window constraints are imposed.     

Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO

Two solution representations for solving the generalized multi-depot vehicle routing problem with multiple pickup and delivery requests (GVRP-MDMPDR) is presented in this paper. The representations are used in conjunction with GLNPSO, a variant of PSO with multiple social learning terms. The computational experiments are carried out using benchmark test instances for pickup and delivery problem with time windows (PDPTW) and the generalized vehicle routing problem for multi-depot with multiple pickup and delivery requests (GVRP-MDMPDR). The preliminary results illustrate that the proposed method is capable of providing good solutions for most of the test problems.     

A Coordination-Based Algorithm for Dedicated Destination Vehicle Routing in B2B E-Commerce

This paper proposes a solution to the open vehicle routing problem with time windows (OVRPTW) considering third-party logistics (3PL). For the typical OVRPTW problem, most researchers consider time windows, capacity, routing limitations, vehicle destination, etc. Most researchers who previously investigated this problem assumed the vehicle would not return to the depot, but did not consider its final destination. However, by considering 3PL in the B2B e-commerce, the vehicle is required back to the nearest 3PL location with available space. This paper formulates the problem as a mixed integer linear programming (MILP) model with the objective of minimizing the total travel distance. A coordinate representation particle swarm optimization (CRPSO) algorithm is developed to obtain the best delivery sequencing and the capacity of each vehicle. Results of the computational study show that the proposed method provides solution within a reasonable amount of time. Finally, the result compared to PSO also indicates that the CRPSO is effective.     

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.     

生鲜电商配送的TDVRPTW研究: 基于经济成本与环境成本兼顾的视角

基于经济成本与环境成本兼顾的视角,研究时变网络下生鲜电商配送的带时间窗车辆路径问题(TDVRPTW),综合考虑车辆时变行驶速度、车辆油耗、碳排放、生鲜农产品的易腐易损性、客户时间窗与最低新鲜度限制等因素,设计跨时间段的路段行驶时间计算方法,引入农产品新鲜度度量函数与碳排放率度量函数.在此基础上,以经济成本与环境成本之和最小为目标构建具有最低新鲜度限制的TDVRPTW数学模型,并根据模型特点设计一种自适应改进蚁群算法求解.最后采用案例验证所提出方法能有效规避交通拥堵时间段、降低总配送成本、促进物流配送领域的节能减排.     

蚂蚁算法在带时间窗车辆路径问题中的应用及参数分析

带时间窗的车辆路径问题是一个典型的NP-Hard问题,本文将蚂蚁算法应用于带时间窗车辆路径问题,构造了该问题的表达方法,建立了相应的算法模型,对算法参数进行了分析并提出了相应的参数改进方案。仿真实验表明,改进后的算法可以快速、有效地求解带时间窗车辆路径问题,具有较好的可行性和适用性。     

Time Windows Based Dynamic Routing in Multi-AGV Systems

This paper presents a dynamic routing method for supervisory control of multiple automated guided vehicles (AGVs) that are traveling within a layout of a given warehouse. In dynamic routing a calculated path particularly depends on the number of currently active AGVs' missions and their priorities. In order to solve the shortest path problem dynamically, the proposed routing method uses time windows in a vector form. For each mission requested by the supervisor, predefined candidate paths are checked if they are feasible. The feasibility of a particular path is evaluated by insertion of appropriate time windows and by performing the windows overlapping tests. The use of time windows makes the algorithm apt for other scheduling and routing problems. Presented simulation results demonstrate efficiency of the proposed dynamic routing. The proposed method has been successfully implemented in the industrial environment in a form of a multiple AGV control system.     

一种求解多校多车型校车路径问题的元启发算法

针对多种车型可用的多校校车路径问题(SBRP),建立数学模型,并提出了一种迭代局部搜索(ILS)元启发算法进行求解。该算法引入并改进了带时间窗的装卸一体化问题(PDPTW)求解中的点对邻域算子,并使用可变邻域下降搜索(VND)完成局部提升。局部提升过程中,设计一种基于路径段的车型调整策略,尽可能地调整车型,降低成本,并允许接受一定偏差范围内的邻域解以保证搜索的多样性。对于局部提升得到的最好解,使用多点移动方法对其进行扰动,以避免算法过早陷入局部最优。在国际基准测试案例上分别测试多校混载和不混载模式下算法的性能,实验结果验证了设计算法的有效性。进一步使用提出的算法求解单车型多校SBRP问题,并与后启发算法、模拟退火算法和记录更新法等算法进行比较,实验结果表明该算法仍然能够获得较好的优化效果。     

基于混合算法的带时间窗的车辆路径问题求解

建立了有时间窗车辆路径问题的数学模型,针对遗传算法在局部搜索能力方面的不足,提出将模拟退火算法与遗传算法相结合,从而构造了有时间窗车辆路径问题的混合遗传算法,并进行了实验计算。结果表明,用混合遗传算法求解该优化问题,可以在一定程度上克服遗传算法在局部搜索能力方面的不足和模拟退火算法在全局搜索能力方面的不足,从而得到了质量较高的解。