包含随机客户的选择性旅行商问题建模及求解

doi:10.12005/orms.2018.0105

摘要/Abstract

摘要： 针对快递配送过程中客户需求具有不确定性的特征,提出一种新的路径优化问题——包含随机客户的选择性旅行商问题,在该问题中客户每天是否具有配送需求存在一定概率,并且对客户进行配送可获取一定利润。同时考虑以上两种因素,建立该问题的数学模型, 目标为在满足行驶距离限制的条件下,找出一条经过部分客户的预优化路径,使得该路径的期望利润最大。其可用于模拟构建最后一公里快递配送的路径问题,提供更具有经济效益的配送路径。随后提出包含精细化局部搜索策略的改进遗传算法,算法根据问题特点构建初始可行解。最后通过多个计算比对结果表明,该算法具有较高的计算效率。

关键词: 旅行商问题, 路径优化, 随机客户, 利润, 遗传算法

Abstract: A new routing problem is introduced and named as the selective traveling salesman problem with stochastic customers. The problem is put forward to address how to deal with stochastic customer presence under the environment in which an associated profit is obtained once a customer is visited. It is defined on a complete graph in which profits are associated with the vertices and travel costs are associated with the edges. Each vertex (customer) has a probability of requiring a visit. It can be used to model the routing problems existed in the direct-to-customer deliveries in the last mile logistics and provide more economic delivery tours. A mathematical formulation is provided after a detailed description of this problem. The objective is to find a subset of customers to visit and a priori tour through those customers which does not violate the maximum expected travel distance constraint and maximizes the expected profit. This problem is NP hard. To solve this complicated problem, an improved genetic algorithm is designed to find the Pareto-optimal solutions, and experiments were conducted on a series of test problems. The computational results show a good performance of the proposed algorithm.

Key words: traveling salesman problem, routing problem, stochastic customers, profit, genetic algorithm

中图分类号:

TP252

张梦颖, 秦进, 梁樑. 包含随机客户的选择性旅行商问题建模及求解[J]. 运筹与管理, 2018, 27(5): 8-14.

ZHANG Meng-ying, QIN Jin, LIANG Liang. Modeling and Solving Selective Traveling Salesman Problem with Stochastic Customers[J]. Operations Research and Management Science, 2018, 27(5): 8-14.

参考文献

[1]Laporte G, Martello S. The selective travelling salesman problem[J]. Discrete Applied Mathematics, 1990, 26(2): 193-207.
[2]Golden B L, Levy L, Vohra R. The orienteering problem[J]. Naval Research Logistics(NRL), 1987, 34(3): 307-318.
[3]Feillet D, Dejax P, Gendreau M. Traveling salesman problems with profits[J]. Transportation Science, 2005, 39(2): 188-205.
[4]Vansteenwegen P, Souffriau W, Oudheusden D V. The orienteering problem: a survey[J]. European Journal of Operational Research, 2011, 209(1): 1-10.
[5]Verbeeck C, Vansteenwegen P, Aghezzaf E H. Solving the stochastic time-dependent orienteering problem with time windows[J]. European Journal of Operational Research, 2016, 255(3): 699-718.
[6]Erdoğan G, Laporte G. The orienteering problem with variable profits[J]. Networks, 2013, 61(2): 104-116.
[7]Campbell A M, Gendreau M, Thomas B W. The orienteering problem with stochastic travel and service times[J]. Annals of Operations Research, 2011,186(1): 61-81.
[8]Zhang S, Ohlmann J W, Thomas B W. A priori orienteering with time windows and stochastic wait times at customers[J]. European Journal of Operational Research, 2014, 239(1): 70-79.
[9]Papapanagiotou V, Montemanni R, Gambardella L M. Objective function evaluation methods for the orienteering problem with stochastic travel and service times[J]. Journal of Applied Operational Research, 2014, 6(1): 16-29.
[10]王文蕊,吴耀华.考虑变动成本的车辆路径问题建模及求解[J].计算机集成制造系统,2014,20(4):979-987.
[11]刘长石,彭怡,寇钢.震后应急物资配送的模糊定位—路径问题研究[J].中国管理科学,2016,24(05):111-118.
[12]Voccia S A, Campbell A M, Thomas B W. The probabilistic traveling salesman problem with time windows[J]. EURO Journal on Transportation and Logistics, 2013, 2(1-2): 89-107.
[13]李锋,魏莹.求解随机旅行时间的C-VRP问题的混合遗传算法[J].系统管理学报,2014,23(6):819-825.
[14]Tas D, Dellaert N, Van W T, et al. Vehicle routing problem with stochastic travel times including soft time windows and service costs[J]. Computers & Operations Research, 2013, 40(1): 214-224.
[15]Tas D, Gendreau M, Dellaert N, et al. Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach[J]. European Journal of Operational Research, 2014, 236(3): 789-799.
[16]Lei H, Laporte G, Guo B. Districting for routing with stochastic customers[J]. EURO Journal on Transportation and Logistics, 2012, 1(1-2): 67-85.
[17]张涛,余绰娅,刘岚,邵志芳,张玥杰.同时送取货的随机旅行时间车辆路径问题方法[J].系统工程理论与实践,2011,31(10):1912-1920.
[18]Laporte G, Louveaux F V, Mercure H. A priori optimization of the probabilistic traveling salesman problem[J]. Operations research, 1994, 42(3), 543-549.
[19]Campbell A M, Thomas B W. Probabilistic traveling salesman problem with deadlines[J]. Transportation Science, 2008, 42(1): 1-21.
[20]Tsiligirides T. Heuristic methods applied to orienteering[J]. Journal of the Operational Research Society, 1984,35(9): 797-809.
[21]Wang Q, Sun X, Golden B L, Jia, J. Using artificial neural networks to solve the orienteering problem[J]. Annals of Operations Research, 1995, 61(1): 111-120.
[22]Chao I M, Golden B L, Wasil E A. A fast and effective heuristic for the orienteering problem[J]. European Journal of Operational Research, 1996, 88(3): 475-489.
[23]Campos V, Martí R, Sánchez-Oro J, Duarte A. GRASP with path relinking for the orienteering problem[J]. Journal of the Operational Research Society, 2014, 65(12): 1800-1813.
[24]Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4): 455-472.
[25]Shaw P. Using constraint programming and local search methods to solve vehicle routing problem. In: Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming. Springer, New York, 1998. 417-431.