In this article, a multi-product inventory routing problem is studied. One-depot and many retailers in a finite time period are considered, and split delivery is allowed as well for the addressed problem. The objectiv...In this article, a multi-product inventory routing problem is studied. One-depot and many retailers in a finite time period are considered, and split delivery is allowed as well for the addressed problem. The objective is to minimize the overall cost including vehicle cost, inventory holding cost and transportation cost while the delivery schedule and the quantity of each product for each retailer have to be decided simultaneously. A mathematical model is presented for solving the addressed optimally and example is illustrated as well.展开更多
In this study,we investigate a forest-based solution representation for split delivery vehicle routing problems(SDVRPs),which have several practical applications and are among the most difficult vehicle routing proble...In this study,we investigate a forest-based solution representation for split delivery vehicle routing problems(SDVRPs),which have several practical applications and are among the most difficult vehicle routing problems.The new solution representation fully reflects the nature of split delivery,and can help reduce the search space when used in heuristic algorithms.Based on the forest structure,we devise three neighborhood search operators.To highlight the effectiveness of this solution representation,we integrate these operators into a standard tabu search framework.We conduct extensive experiments on three main SDVRPs addressed in the literature:The basic SDVRP,the multidepot SDVRP,and the SDVRP with time windows.The experimental results show that the new forest-based solution representation is particularly effective in designing and implementing neighborhood operators,and that our new approach outperforms state-of-the-art algorithms on standard datasets.展开更多
The vehicle routing problem(VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the res...The vehicle routing problem(VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups(VRPSPDP) is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.展开更多
Fresh agri-product emergency supply is crucial to secure the basic livelihood of residents at large-scale epidemic disease context. Considering the massive demand and limited transportation resources, this study integ...Fresh agri-product emergency supply is crucial to secure the basic livelihood of residents at large-scale epidemic disease context. Considering the massive demand and limited transportation resources, this study integrates multi-item packaging and vehicle routing with split delivery to improve the emergency supply capacity. Firstly, three specific objectives of fresh agri-product emergency supply at large-scale epidemic disease context are formulated, i.e., average response time, infectious risk possibility and transportation resource utilization. Then, a multi-item packaging strategy is proposed to consolidate different categories of fresh agri-products according to the food cold chain temperatures.An optimization model integrating multi-item packaging and vehicle routing with split delivery is developed to jointly decide the optimal packaging scheduling, vehicle assignment and delivery routing. Next, an improved genetic algorithm based on solution features (IGA-SF) is designed to solve the integrated model with multiple decision variables. Finally,a case on fresh agri-product emergency supply of Huangpi District, Wuhan in the context of the Corona Virus Disease 2019(COVID-19) is carried out to illustrate the efficiency and feasibility of the proposed model. The numerical results of medium-to-largescale cases demonstrate that the proposed IGA-SF could save 23.91% CPU time and 37.80% iteration number on average than genetic algorithm. This study could satisfy different emergency scenario requirements flexibly, and provide scientific decision support for provincial and national governments on fresh agri-product emergency supply.展开更多
We study a variety of multi-vehicle generalizations of the Stacker Crane Problem(SCP).The input consists of a mixed graph G=(V,E,A)with vertex set V,edge set E and arc set A,and a nonnegative integer cost function c o...We study a variety of multi-vehicle generalizations of the Stacker Crane Problem(SCP).The input consists of a mixed graph G=(V,E,A)with vertex set V,edge set E and arc set A,and a nonnegative integer cost function c on E∪A.We consider the following three problems:(1)k-depot SCP(k-DSCP).There is a depot set D⊆V containing k distinct depots.The goal is to determine a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized,where each closed walk corresponds to the route of one vehicle and has to start from a distinct depot and return to it.(2)k-SCP.There are no given depots,and each vehicle may start from any vertex and then go back to it.The objective is to find a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized.(3)k-depot Stacker Crane Path Problem(k-DSCPP).There is a depot set D⊆V containing k distinct depots.The aim is to find k(open)walks including all the arcs of A such that the total cost of the walks is minimized,where each(open)walk has to start from a distinct depot but may end at any vertex.We present the first constant-factor approximation algorithms for all the above three problems.To be specific,we give 3-approximation algorithms for the k-DSCP,the k-SCP and the k-DSCPP.If the costs of the arcs are symmetric,i.e.,for every arc there is a parallel edge of no greater cost,we develop better algorithms with approximation ratios max{9/5,2−1/2k+1},2,2,respectively.All the proposed algorithms have a time complexity of O(|V|3)except that the two 2-approximation algorithms run in O(|V|2log|V|)time.展开更多
针对带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSPDTW),构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型,提出自适应头脑风暴算法(ada...针对带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSPDTW),构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型,提出自适应头脑风暴算法(adaptive brain storm optimization,ABSO)进行求解。全局搜索阶段,采用多项惩罚方式扩大搜索区域,并使用聚类及三种路径搜索策略进行全局搜索;局部搜索阶段,将六种破坏-修复算子作为备选集合,进而设计自适应动态选择邻域搜索机制,增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试,实验结果表明针对小规模标准算例,所提算法全部取得了当前已知最优解;对于大规模标准算例,通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比,所提算法实验计算结果有7.52%~12.03%的提升;对于实际案例,所提算法在收敛速度和寻优能力方面均展示出优越性,充分验证了所提算法对解决VRPSPDTW问题的有效性。展开更多
文摘In this article, a multi-product inventory routing problem is studied. One-depot and many retailers in a finite time period are considered, and split delivery is allowed as well for the addressed problem. The objective is to minimize the overall cost including vehicle cost, inventory holding cost and transportation cost while the delivery schedule and the quantity of each product for each retailer have to be decided simultaneously. A mathematical model is presented for solving the addressed optimally and example is illustrated as well.
文摘In this study,we investigate a forest-based solution representation for split delivery vehicle routing problems(SDVRPs),which have several practical applications and are among the most difficult vehicle routing problems.The new solution representation fully reflects the nature of split delivery,and can help reduce the search space when used in heuristic algorithms.Based on the forest structure,we devise three neighborhood search operators.To highlight the effectiveness of this solution representation,we integrate these operators into a standard tabu search framework.We conduct extensive experiments on three main SDVRPs addressed in the literature:The basic SDVRP,the multidepot SDVRP,and the SDVRP with time windows.The experimental results show that the new forest-based solution representation is particularly effective in designing and implementing neighborhood operators,and that our new approach outperforms state-of-the-art algorithms on standard datasets.
基金Project supported by the National Natural Science Foundation of China(No.51138003)the National Social Science Foundation of Chongqing of China(No.2013YBJJ035)
文摘The vehicle routing problem(VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups(VRPSPDP) is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.
基金supported by National Natural Science Foundation of China (71803084)Humanity and Social Science Youth Foundation of Ministry of Education of China (17YJC630048)Fundamental Research Funds for the Central Universities (NJAU: SKCX2020009)。
文摘Fresh agri-product emergency supply is crucial to secure the basic livelihood of residents at large-scale epidemic disease context. Considering the massive demand and limited transportation resources, this study integrates multi-item packaging and vehicle routing with split delivery to improve the emergency supply capacity. Firstly, three specific objectives of fresh agri-product emergency supply at large-scale epidemic disease context are formulated, i.e., average response time, infectious risk possibility and transportation resource utilization. Then, a multi-item packaging strategy is proposed to consolidate different categories of fresh agri-products according to the food cold chain temperatures.An optimization model integrating multi-item packaging and vehicle routing with split delivery is developed to jointly decide the optimal packaging scheduling, vehicle assignment and delivery routing. Next, an improved genetic algorithm based on solution features (IGA-SF) is designed to solve the integrated model with multiple decision variables. Finally,a case on fresh agri-product emergency supply of Huangpi District, Wuhan in the context of the Corona Virus Disease 2019(COVID-19) is carried out to illustrate the efficiency and feasibility of the proposed model. The numerical results of medium-to-largescale cases demonstrate that the proposed IGA-SF could save 23.91% CPU time and 37.80% iteration number on average than genetic algorithm. This study could satisfy different emergency scenario requirements flexibly, and provide scientific decision support for provincial and national governments on fresh agri-product emergency supply.
基金This research was supported by the National Natural Science Foundation of China(Nos.11671135 and 11871213)the Natural Science Foundation of Shanghai(No.19ZR1411800)。
文摘We study a variety of multi-vehicle generalizations of the Stacker Crane Problem(SCP).The input consists of a mixed graph G=(V,E,A)with vertex set V,edge set E and arc set A,and a nonnegative integer cost function c on E∪A.We consider the following three problems:(1)k-depot SCP(k-DSCP).There is a depot set D⊆V containing k distinct depots.The goal is to determine a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized,where each closed walk corresponds to the route of one vehicle and has to start from a distinct depot and return to it.(2)k-SCP.There are no given depots,and each vehicle may start from any vertex and then go back to it.The objective is to find a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized.(3)k-depot Stacker Crane Path Problem(k-DSCPP).There is a depot set D⊆V containing k distinct depots.The aim is to find k(open)walks including all the arcs of A such that the total cost of the walks is minimized,where each(open)walk has to start from a distinct depot but may end at any vertex.We present the first constant-factor approximation algorithms for all the above three problems.To be specific,we give 3-approximation algorithms for the k-DSCP,the k-SCP and the k-DSCPP.If the costs of the arcs are symmetric,i.e.,for every arc there is a parallel edge of no greater cost,we develop better algorithms with approximation ratios max{9/5,2−1/2k+1},2,2,respectively.All the proposed algorithms have a time complexity of O(|V|3)except that the two 2-approximation algorithms run in O(|V|2log|V|)time.
文摘针对带时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pickup-delivery and time windows,VRPSPDTW),构建了以车辆使用成本、车辆行驶距离成本总支出最小化的路径优化数学模型,提出自适应头脑风暴算法(adaptive brain storm optimization,ABSO)进行求解。全局搜索阶段,采用多项惩罚方式扩大搜索区域,并使用聚类及三种路径搜索策略进行全局搜索;局部搜索阶段,将六种破坏-修复算子作为备选集合,进而设计自适应动态选择邻域搜索机制,增强局部搜索效能。选取测试数据集和实际案例对算法性能进行测试,实验结果表明针对小规模标准算例,所提算法全部取得了当前已知最优解;对于大规模标准算例,通过与遗传算法、并行模拟退火算法、离散布谷鸟算法对比,所提算法实验计算结果有7.52%~12.03%的提升;对于实际案例,所提算法在收敛速度和寻优能力方面均展示出优越性,充分验证了所提算法对解决VRPSPDTW问题的有效性。