随机旅行售货员问题的建模与求解

随机旅行售货员问题的建模与求解

1旅行售货员问题的描述物流经理问题是在运营中的一个著名建议，属于组合优化问题。当所考虑的问题规模不大时,利用动态规划(DynamicProgramming)方法求解非常方便【1-2】。早期关于旅行售货员问题的讨论总是基于无向图展开的,对应的旅行售货员问题我们称之为传统的旅行售货员问题。事实上,由于单行线或者上下行路线的坡度等原因,这一问题有时必须借助于有向图来进行研究和解决,我们称之为广义的旅行售货员问题。甚至有时还需要考虑参数(距离或者时间等)为随机变量的随机旅行售货员问题。到目前为止,对旅行售货员问题的研究主要是从图论角度展开的,给出的多数都是各种启发式算法或者递推算法,近年来一些典型的研究成果见文献[3-18]。本文将从数学规划的角度进行研究。数学规划建模具有借助软件包求解方便、易于修改和推广等多方面的优点,即使对于大型问题也易于解决。本文首先就一般意义下的旅行售货员问题建立了相应的显式整数规划模型,并将这一模型推广至基于有向图的广义情形和参数为随机变量的随机情形,相应地给出了若干数值例示以说明这些模型的有效性。2最优旅行路线的确定传统的旅行售货员问题可以概述如下:设有n个城市,以V1,V2,…,Vn表示之,用dij表示城市Vi到城市Vj之间的距离,一个推销员从某城市(不妨假设从城市V1)出发到其他城市去一次而且仅一次,然后回到原来的城市(城市V1),问其应该选择什么样的行走路线才能使得总的旅行路程最短。把这个问题抽象成图论问题就是给定一个连通无向图G(V,E),其中V={V1,V2,…,Vn}是顶点(城市)的集合,E是顶点间边的集合,表示相应城市间的旅行路线,即E={e=(Vi,Vj);顶点Vi与Vj间有边e},每个边e∈E上有非负权重w(e)=w(Vi,Vj)=dij,表示顶点Vi即城市Vi到顶点Vj(即城市Vj)的距离,问题就是要确定图G的一个圈,它过每个顶点一次且仅一次,而且使得该圈的总权(即圈上所有边的权之和)最小。这个圈在图论里称为Hamilton圈,简称H圈。为叙述方便,若e=(Vi,Vj),则记为ei,j∈E,而相应地添加边为ej,i。与边ei,j∈E′相对应,设定一个0-1整数变量xi,j。若ei,j∈E′,即称边是从Vi到Vj的,或称为弧。这样,我们就可以把无向图理解为有向图D(V,E)。每一个E1哿E′唯一对应一组xi,j的值,反之亦然。我们称xi,j为E1的值系。在给出旅行售货员问题的数学规划之前,我们不加证明地引用如下结果:引理D(V,E)没有简单圈当且仅当存在一组:使得ui-uj+nxi,j≤n-1,i≠j,(Vi,Vj)∈E其中xi,j为E的值系。借助上述引理可以定义最优旅行路线问题的约束如下:(1)过每个顶点一次且仅一次,xi,j应该满足:(2)图D(V,E1)为H圈即为简单圈,因此去掉任一顶点(如V1)以及相邻边((Vi,Vj)∈E1,(Vi,Vj)∈E1)所剩的图为连通图且不包含简单圈,故E1的值系xi,j满足:存在一组使得ui-uj+(n-1)xi,j≤n-2,i≠j≠1,(Vi,Vj)∈E,这一问题的目标是使得G1(V,E1)的总权最小,即式中,wi,j为边ei,j上的权,wj,i=wi,j。这样,我们就得到旅行售货员问题的显式整数规划模型(TSP)如下:这一模型不仅可以用来求解旅行售货员问题,而且还可利用“递推法”确定相应的最优旅行路线:如xi,j=1,即表示售货员应该从Vi沿着边(即交通线路)ei,j到Vj。【例1】考虑如图1所示的4城市旅行售货员问题对应的整数规划模型如下:应用QSB整数规划软件,求解上述模型得到:最小权重为23。假定售货员所在地为V1,则有下列最优旅行路线:V1→V4→V3→V2→V1同理可以求得售货员在任何一顶点城市时的最优旅行路线,如售货员在城市V2,相应的最优旅行路线为:V2→V1→V4→V3→V2,最优权重也为23。3广义旅行售货员问题前节所述的旅行售货员问题假定了其旅行范围内的每一条线路(边)的上行和下行是无差别的,而在实际旅行过程中可能不是这样的,如遇到单行线、旅行受旅行工具的可用性影响等。这样的旅行售货员问题我们称之为广义的旅行售货员问题。这一广义的旅行售货员问题也可以抽象为一个有向图问题。类似于前面所述的传统旅行售货员问题,广义旅行售货员问题可以抽象为如下图论问题:给定一个连通有向图G(V,E),每一个弧e上有一非负权w(e),需要寻找G的一个回路,它过每个顶点一次且仅一次,且使得总权为最小。类似前节的分析,对于G(V,E)的每条弧ei,j∈E定义一个0-1整数变量xi,j,有如下广义旅行售货员问题的显式整数规划模型(GTSP):通过对这一模型的求解,可以得到广义旅行售货员问题的最优旅行路线。【例2】求解下列6城市的旅行售货员问题,其中的距离矩阵如表1所示。这一问题的整数数学规划模型如下:最小权重为80。假定售货员所在地为V1(城市1),则有下列最优旅行路线:V1→V2→V6→V5→V4→V3→V1。同理可以求得售货员在任何一个城市时的最优旅行路线,如售货员在城市V6,相应的最有旅行路线为:V6→V5→V4→V3→V1→V2→V6。最短旅行路线的长度仍然为80。4随机规划理论上述讨论的传统的和广义的旅行售货员问题都假定与边或者弧相联系的权重是确定的常数。实际中经常遇到权重非固定的情况,如考虑的权重是旅行时间,由于所选旅行工具的不同或者天气等方面的原因,旅行的时间会有所变动,但一般会遵循某种变化规律,即权重是具有某种分布的随机变量,这时我们称对应的问题为随机旅行售货员问题。对这一随机问题,常用的动态规划方法已经无能为力,但借助于本文建立的整数规划模型,应用随机规划理论,可以很方便地处理这一问题。随机问题的处理方法有多种,如期望值法、机会约束法、最优值分布法、相关机会约束法、多阶段(如二阶段)法。本文在此仅讨论机会约束法,其核心是概率约束条件的确定型等价处理。注意到,TSP或者GTSP的约束中都不含有权重参数,因此处理权重随机的问题只需要将目标函数做相应的确定型等价处理即可。权重随机时,目标函数也是随机变量,根据随机规划理论,随机的TSP问题可以转化为如下两个确定型等价模型:其中1-TSP(α)指对固定的α求解xi,j以及w。而2-TSP(w)指对固定的w求解xi,j和α。此处,我们称α为权重w的可行度,w为总权重的希望水平。如果诸权重均服从正态分布而且相互独立,wi,j服从N(μi,j,σ2i,j),则1-TSP(α)和2-TSP(w)分别等价于下列两个数学规划:其中F(X)为标准正态累积分布函数,F-1(y)为其逆函数。进一步,可分别等价于如下两个数学规划问题:其中注意到F-1(α)是α的单调递增函数。对于其他类型的随机问题也可以类似地进行分析。注意:上述规划是非线性的,因此需要借助非线性整数规划的求解工具和软件或者两阶段法等进行求解,大型问题也可以借助于现代智能优化算法进行求解。对于广义旅行售货员问题也可以类似讨论相应的随机问题,在此从略。5基于不确定性的转化本文基于传统的旅行售货员问题,建立了这一问题的显式整数规划模型,并将之推广到基于赋权有向图的广义旅行售货员问题和权重不确定的随机旅行售货员问题。另外一些可能的推广是考虑权重是模糊型(Fuzzy)或者灰色型(Grey)或者粗糙型(Co