同时集散货物的开放式车辆路径问题研究  

Research on the Open Vehicle Routing Problemof with Simultaneous Deliveries and Pickups

作　　者：张江华[1] 李进[2] 高敏刚[3] 

机构地区：[1]山东大学管理学院,山东济南250100 [2]浙江工商大学信息学院,浙江杭州310018 [3]中国科学院科技政策与管理科学研究所,北京100190

出　　处：《中国管理科学》2013年第4期187-192,共6页Chinese Journal of Management Science

基　　金：国家自然科学基金资助项目(71201093);山东省优秀中青年科学家科研奖励基金项目(BS2012SF012);教育部人文社科青年项目(12YJC630091);浙江省自然科学基金项目(LQ12G02007);山东大学自主创新基金项目(2012TS194)

摘　　要：本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。Open vehicle routing problem of multiple distribution centers with simultaneous deliveries and pickups is studied, in which the number and working time of the vehicles are limited. Based on the minimum number and travel distance of vehicles, a multi-objective model is proposed. A novel mixed algorithm based on lagrangian relaxation technique and tabu search algorithm is given, which obtains the maximum lower bound of the optimal solution and then adopts the strategy of assignment and adiustment for clients to achieve the feasible solution. For the tabu search algorithm, a random neighborhood ordering and perturbation mechanisms based on four neighborhood search methods are employed. Computational results show that this algorithm is effective to search the satisfactory solutions and the open collaborative arrangement of vehicle routing is more economic and reasonable than the close independent arrangement of vehicle routing.

关 键 词：车辆路径问题 同时集散货物 模型与算法 

分 类 号：F505[经济管理—产业经济]