计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (1): 271-278.DOI: 10.3778/j.issn.1002-8331.2006-0317

• 工程与应用 • 上一篇    

生鲜电商配送的开放式时变车辆路径问题研究

付朝晖,刘长石   

  1. 1.长沙民政职业技术学院 软件学院,长沙 410004
    2.湖南工商大学 工商管理学院,长沙 410205
  • 出版日期:2021-01-01 发布日期:2020-12-31

Research on Open Time-Dependent Vehicle Routing Problem of Fresh Food E-commerce Distribution

FU Zhaohui, LIU Changshi   

  1. 1.School of Software, Changsha Social Work College, Changsha 410004, China
    2.School of Management, Hunan University of Technology and Business, Changsha 410205, China
  • Online:2021-01-01 Published:2020-12-31

摘要:

针对生鲜电商配送的“最后一公里”难题,考虑到生鲜农产品的易腐易损性与生鲜电商通常采用普通车辆配送等现实情况,引入常温条件下生鲜农产品的鲜活度度量函数;分析城市路网的时变特性,设计时变路网条件下的车辆行驶时间计算方法;综合考虑客户需求量、时间窗、生鲜农产品送达客户时的鲜活度、开放式车辆路径与车辆灵活出发时间等因素,以总配送成本最小为目标构建具有鲜活度限制的开放式时变车辆路径问题优化模型,并根据模型特点设计一种改进蚁群算法求解。仿真实验结果表明:与封闭式车辆路径策略相比较,基于开放式车辆路径策略的改进蚁群算法能有效降低生鲜电商的总配送成本,减少车辆使用数量,缩短车辆行驶距离,具有合理性与可行性。

关键词: 时变路网, 生鲜农产品, 开放式车辆路径问题, 改进蚁群算法

Abstract:

The “last kilometer” difficulty of fresh food e-commerce distribution is considered. The measurement function of fresh agricultural products under normal temperature is employed by considering the perishability of fresh agricultural products and that fresh agricultural products are usually distributed by ordinary vehicles. In view of the time-dependent characteristics of urban road network, the calculation method of vehicle travel time under the condition of time-dependent road network is designed. A model of the Open Time-Dependent Vehicle Routing Problem(OTDVRP) is formulated for fresh agricultural products distribution with minimum freshness by considering the factors such as customer demand, time window, freshness of fresh agricultural product delivered to customers, open vehicle routing and flexible vehicle departure time. The objective of the OTDVRP model is to minimize the total distribution cost. An improved ant colony algorithm is designed to solve the problem. Finally, the rationality and effectiveness of the proposed approaches are verified by extensive experimental results. The simulation results show that compared with the closed vehicle routing strategy, the improved ant colony algorithm based on the open vehicle routing strategy can effectively reduce the total distribution cost of fresh food e-commerce, the number of vehicles used and shorten the distance of vehicles. The proposed approaches are reasonable and feasible.

Key words: time-dependent road network, fresh agricultural products, open vehicle routing problem, improved ant colony algorithm