Most research on the Vehicle Routing Problem （VRP） is focused on standard conditions, which is not suitable for specific cases. A Hybrid Genetic Algorithm is proposed to solve a Vehicle Routing Problem （VRP） with ...Most research on the Vehicle Routing Problem （VRP） is focused on standard conditions, which is not suitable for specific cases. A Hybrid Genetic Algorithm is proposed to solve a Vehicle Routing Problem （VRP） with complex side constraints. A novel coding method is designed especially for side constraints. A greedy algorithm combined with a random algorithm is introduced to enable the diversity of the initial population, as well as a local optimization algorithm employed to improve the searching efficiency. In order to evaluate the performance, this mechanism has been implemented in an oil distribution center, the experimental and executing results show that the near global optimal solution can be easily and quickly obtained by this method, and the solution is definitely satisfactory in the VRP application.展开更多
A novel approximation algorithm was proposed for the problem of finding the minimum total cost of all routes in Capacity Vehicle Routing Problem (CVRP). CVRP can be partitioned into three parts: the selection of vehic...A novel approximation algorithm was proposed for the problem of finding the minimum total cost of all routes in Capacity Vehicle Routing Problem (CVRP). CVRP can be partitioned into three parts: the selection of vehicles among the available vehicles, the initial routing of the selected fleet and the routing optimization. Fuzzy C-means (FCM) can group the customers with close Euclidean distance into the same vehicle according to the principle of similar feature partition. Transiently chaotic neural network (TCNN) combines local search and global search, possessing high search efficiency. It will solve the routes to near optimality. A simple tabu search (TS) procedure can improve the routes to more optimality. The computations on benchmark problems and comparisons with other results in literatures show that the proposed algorithm is a viable and effective approach for CVRP.展开更多
We investigate a kind of vehicle routing problem with constraints(VRPC)in the car-sharing mobility environment,where the problem is based on user orders,and each order has a reservation time limit and two location poi...We investigate a kind of vehicle routing problem with constraints(VRPC)in the car-sharing mobility environment,where the problem is based on user orders,and each order has a reservation time limit and two location point transitions,origin and destination.It is a typical extended vehicle routing problem(VRP)with both time and space constraints.We consider the VRPC problem characteristics and establish a vehicle scheduling model to minimize operating costs and maximize user(or passenger)experience.To solve the scheduling model more accurately,a spatiotemporal distance representation function is defined based on the temporal and spatial properties of the customer,and a spatiotemporal distance embedded hybrid ant colony algorithm(HACA-ST)is proposed.The algorithm can be divided into two stages.First,through spatiotemporal clustering,the spatiotemporal distance between users is the main measure used to classify customers in categories,which helps provide heuristic information for problem solving.Second,an improved ant colony algorithm(ACO)is proposed to optimize the solution by combining a labor division strategy and the spatiotemporal distance function to obtain the final scheduling route.Computational analysis is carried out based on existing data sets and simulated urban instances.Compared with other heuristic algorithms,HACA-ST reduces the length of the shortest route by 2%–14%in benchmark instances.In VRPC testing instances,concerning the combined cost,HACA-ST has competitive cost compared to existing VRP-related algorithms.Finally,we provide two actual urban scenarios to further verify the effectiveness of the proposed algorithm.展开更多
针对有服务顺序限制的带时间窗的多需求多目标车辆路径问题(multi-demand and multi-objective vehicle routing problem with time window,MDMOVRPTW),在考虑多种需求由不同车辆按顺序服务等约束条件的同时,构建了最小化配送成本和最...针对有服务顺序限制的带时间窗的多需求多目标车辆路径问题(multi-demand and multi-objective vehicle routing problem with time window,MDMOVRPTW),在考虑多种需求由不同车辆按顺序服务等约束条件的同时,构建了最小化配送成本和最大化客户满意度的多目标模型。根据模型的特点设计了改进的哈里斯鹰优化(improved Harris hawks optimization,IHHO)算法,随机地将种群中部分支配解作为父代解,用临时组合算子和4种交叉算子搜索新解。最后,算例测试结果表明,相较于传统的哈里斯鹰优化算法,IHHO算法的求解性能得到了有效改善,各操作算子中交叉算子2的求解效果最好。将IHHO算法用于实例中,求解结果得到了改善,充分验证了IHHO算法的有效性。展开更多
基金This paper is supported by High-Tech Research and Development Program of China (Grant No. 2003AA001048) Young Teacher Foundation of School of Electronics and Information Engineering of Xi'an Jiaotong Univeristy.
文摘Most research on the Vehicle Routing Problem （VRP） is focused on standard conditions, which is not suitable for specific cases. A Hybrid Genetic Algorithm is proposed to solve a Vehicle Routing Problem （VRP） with complex side constraints. A novel coding method is designed especially for side constraints. A greedy algorithm combined with a random algorithm is introduced to enable the diversity of the initial population, as well as a local optimization algorithm employed to improve the searching efficiency. In order to evaluate the performance, this mechanism has been implemented in an oil distribution center, the experimental and executing results show that the near global optimal solution can be easily and quickly obtained by this method, and the solution is definitely satisfactory in the VRP application.
文摘A novel approximation algorithm was proposed for the problem of finding the minimum total cost of all routes in Capacity Vehicle Routing Problem (CVRP). CVRP can be partitioned into three parts: the selection of vehicles among the available vehicles, the initial routing of the selected fleet and the routing optimization. Fuzzy C-means (FCM) can group the customers with close Euclidean distance into the same vehicle according to the principle of similar feature partition. Transiently chaotic neural network (TCNN) combines local search and global search, possessing high search efficiency. It will solve the routes to near optimality. A simple tabu search (TS) procedure can improve the routes to more optimality. The computations on benchmark problems and comparisons with other results in literatures show that the proposed algorithm is a viable and effective approach for CVRP.
基金Project supported by the National Science and Technology Innovation 2030 Major Project of the Ministry of Science and Technology of China(No.2018AAA0101200)。
文摘We investigate a kind of vehicle routing problem with constraints(VRPC)in the car-sharing mobility environment,where the problem is based on user orders,and each order has a reservation time limit and two location point transitions,origin and destination.It is a typical extended vehicle routing problem(VRP)with both time and space constraints.We consider the VRPC problem characteristics and establish a vehicle scheduling model to minimize operating costs and maximize user(or passenger)experience.To solve the scheduling model more accurately,a spatiotemporal distance representation function is defined based on the temporal and spatial properties of the customer,and a spatiotemporal distance embedded hybrid ant colony algorithm(HACA-ST)is proposed.The algorithm can be divided into two stages.First,through spatiotemporal clustering,the spatiotemporal distance between users is the main measure used to classify customers in categories,which helps provide heuristic information for problem solving.Second,an improved ant colony algorithm(ACO)is proposed to optimize the solution by combining a labor division strategy and the spatiotemporal distance function to obtain the final scheduling route.Computational analysis is carried out based on existing data sets and simulated urban instances.Compared with other heuristic algorithms,HACA-ST reduces the length of the shortest route by 2%–14%in benchmark instances.In VRPC testing instances,concerning the combined cost,HACA-ST has competitive cost compared to existing VRP-related algorithms.Finally,we provide two actual urban scenarios to further verify the effectiveness of the proposed algorithm.
文摘针对有服务顺序限制的带时间窗的多需求多目标车辆路径问题(multi-demand and multi-objective vehicle routing problem with time window,MDMOVRPTW),在考虑多种需求由不同车辆按顺序服务等约束条件的同时,构建了最小化配送成本和最大化客户满意度的多目标模型。根据模型的特点设计了改进的哈里斯鹰优化(improved Harris hawks optimization,IHHO)算法,随机地将种群中部分支配解作为父代解,用临时组合算子和4种交叉算子搜索新解。最后,算例测试结果表明,相较于传统的哈里斯鹰优化算法,IHHO算法的求解性能得到了有效改善,各操作算子中交叉算子2的求解效果最好。将IHHO算法用于实例中,求解结果得到了改善,充分验证了IHHO算法的有效性。
