论文带退货周期车辆路径问题C—W节约算法是关于对写作W节约算法论文范文与课题研究的大学硕士、相关本科毕业论文c-w节约算法代码论文开题报告范文和相关文献综述及职称论文参考文献资料下载有帮助。
摘 要：文章用MATLAB代码给出了一个改进的C-W节约算法来求解带退货的周期车辆路径问题,目标是最小化周期内总的行驶费用和总的启动费用之和,并举例对算法进行了说明.
关键词：运筹学；周期车辆路径问题；C-W节约算法
中图分类号：U116.2 文献标识码：A
Abstract： In this paper, an improved C-W saving algorithm is given by MATLAB codes to solve the periodic vehicle routing problem with backhauls, aiming to minimize the sum of the total travel expenses and the total startup cost over the planning horizon, an example is gives to illustrate the algorithm.
Key words： operations research； periodic vehicle routing problem； C-W saving algorithm
0 引 言
周期车辆路径问题（Period Vehicle Routing Problem, PVRP）是车辆路径问题（Vehicle Routing Problem, VRP）的一个重要的分支,最早由Beltrami和Bodin[1]于1974年提出,是VRP在时间上的扩展,而由于企业很多计划都是按一定的周期来制定的,所以PVRP有着很强的实用价值,因此到目前为止国内外对其进行的研究已有很多成果：Ann和Jill[2]对国外从1974到2012年这方面的文献以及2013年的部分文献进行了详细综述,之后又有10多篇文献[3-13]对PVRP进行了研究.国内学者在VRP领域进行了大量的研究,但目前对PVRP方面的研究还比较少：姜贵山[14]设计了改进的引导邻域搜索算法、蔡婉君等[15]给出了改进的蚁群算法来求解PVRP.以上这些文献可分为两种类型：（1）只送货的PVRP问题；（2）带取送货（pickup and delivering）的PVRP.其中只有文献[10]和[16]是研究类型（2）的,然而近年来,保障商品质量、上架及时和退货服务成为电商及大型连锁超市应对激烈的市场竞争的关键所在,而在这一过程中物流配送是核心环节,因此受到了高度的关注.另外,不同种类货物的销售多受地域影响,以及消费者维权意识的增强,使得超市间货物调换和产品退回事件趋于普遍,这就要求发展逆向物流配送系统,因此,本文研究了一个带退货的PVRP,该问题隶属于类型（2）中带同时取送货的PVRP,而且要求每个客户在其被服务的各个时间段里取货和送货任务都由一辆车来完成,这和文献[10]和[16]研究的问题都有所不同.
1 问题描述及数学模型
1.1 问题描述
在一个区域内有一个配送站点（车场）,m个顾客,一个周期中有T个时间段,顾客ll等于1,2,等,m在周期内要求的服务次数（以下简称频率）为f0当各个顾客的退货量都是零时上述问题就是传统的PVRP,因此传统的PVRP是本文所讨论问题时的子问题.因PVRP是NP-hard的,所以本文的问题也是NP-hard的.
1.2 数学模型
令N为顾客点集合,N等于1,2,3,等,m,0表示车场；A为弧的集合,a为连接客户点i和j的弧；d和c分别表示i和j之间距离和单位距离的运输费用（当i等于j时,d等于0, c等于0）；K表示所有车辆集合；Q和C分别表示每辆车的车载限制和一次性启动费用；在周期为T个时间段计划中,f表示客户i要求的频率,分别表示客户i在第t个时间段t∈T的需求量和退货量.模型中决策变量为：w表示第t天弧a上的车载量.
式（1）的第一项为总的行驶费用,第二项为总的启动费用；式（2）保证对每一个客户点总访问次数等于其要求频率；式（3）表示被一辆车依次服务的两个客户点必须被安排在同一个时间段；式（4）为流平衡约束：在第tt等于1,等,T个时间段进入某点的车辆数等于从此点出去的车辆数；式（5）表示分配到每一个时间段的所有客户点在该时间段都被访问到；式（6）为子回路消去约束；式（7）表示一辆车在一个时间段内最多只被用一次；式（8）至式（10）表示车辆在行驶过程中的车容量约束；式（11）至式（13）定义变量的取值范围.
2 问题求解
姜贵山[20]设计改进的引导邻域搜索算法中,提出应用C-W节约算法构建PVRP的初始可行解.本文对此算法做出进一步改进,得到解决本问题的改进C-W 节约算法,下面用Matlab代码给出该算法.
function [solution, Customers_just_information]等于Modified_CW_SAT,m,f,M,p,q,Q本函数Modified_CW_SA为求解带退货的周期车辆路径问题的修改C-W节约算法.
T,m,Q： 分别存储周期长度、客户数量、车辆容量；f： 是一个1×m矩阵,存储所有客户的频率；M： 是一个m×m矩阵, 存储所有客户间的节约值；p,q： 都是T×m矩阵, 分别存储每个时间段所有客户的需求量和退货量；solution：是一个T行m+1列的元胞数组,各行第一个元素存储该行对应时间段路径总数,其余元素分别存储该行对应时间段里的各条路径； Customers_just_information： 是一个m行2列的元胞数组, 其第i行第1个元素Customers_just_informationi,1存储一个1×T矩阵,该矩阵的第j个元素Customers_just_informationi,1j等于0或1,前者和后者分别表示第i个客户在第j个时间段没有被服务和已经被服务,Customers_just_information的第i行第2个元素Customers_just_informationi,2存储一个T×3 矩阵,该矩阵的第t行第1-3个元素Customers_just_informationi,2t,s,s等于1,2,3依次存储第i个客户在第t个时间段所在的路径（在第k条路径上就存k）、在该路径上的位置（是该路径上第u个客户点就存u）、该路径的长度.
总结:本论文可用于W节约算法论文范文参考下载，W节约算法相关论文写作参考研究。
参考文献：
1、 有时间窗的车辆路径问题改进蚁群算法 摘 要：针对目前蚁群算法在求解有时间窗的车辆路径问题上较少对蚁群算法本身进行优化的问题，提出了一种改进蚁群算法，通过改进状态转移概率和信息素更新。
2、 扫描法在车辆路径问题中应用 摘 要：随着经济的高速发展，物流行业发展也进入了加速前进的步伐中，而想要在加速前进中不被时代落下，就必须不断优化物流环节，使总成本达到最小化。物。
3、 带时间窗的冷链物流车辆路径优化问题 摘 要：文章研究了带有硬时间窗限制的超市速冻食品冷链配送车辆路径优化问题，根据其配送批量小，配送地点分散，时间要求高的特点建立了配送成本最小的目。
4、 蜂群优化算法在带软时间窗的车辆路径问题中的应用 摘 要:本文给出了带软时间窗的车辆路径问题的一种新的算法,蜂群算法。通过计算若干benchmark问题,并将结果与硬时间窗的目前最好解及蚁群算法。
5、 快件揽收实时车辆路径问题一种贪婪算法 摘要：快递运营中，调派车辆前往随机发生的快件发件人处上门揽收快件，是一个实时编排行车路径的动态决策过程，本文针对该问题，采用了揽收所有快件的最后。
6、 考虑客户满意度同时收发车辆路径问题 摘要：当客户要求车辆一次性完成发送以及收集货物的任务时，只需考虑车辆的路径安排即可。但若客户进一步提出在时间窗内完成的话，就必须考虑客户的等待时。