论文部分内容阅读
【摘要】多车型多路径的单个配送中心的车辆调度优化是城市配送中的典型问题.针对该问题，本文从空驶成本、运输成本两个维度构建了一个VRP的数学模型，并采用爬山算法对模型加以求解.通过实例仿真，获得其最低运输成本的方案.
【关键词】车辆调度；物流配送；多车型
【中图分类号】U492.2 【文献标识码】A
配送车辆调度问题是运筹学和组合优化领域的热点问题.多车型配送车辆调度问题是配送车辆调度问题的一个分支，一般情况下，配送企业为了适应配送商品种类繁多、性质各异、客户要求各不相同的情况，往往配置多种类型的配送车辆，以提高车辆的满载率，降低配送成本.可见，研究多车型配送车辆调度问题具有重要的理论和现实意义.
本文在现有研究成果的基础上，建立了多车型配送车辆调度问题的基于直观描述的数学模型，考虑的目标函数和约束条件比较接近实际，决策变量、目标函数和约束条件的表示较为自然、直观和易于理解.
1.对多车型配送车辆调度问题的描述
现实中的多车型配送车辆调度问题十分复杂，为了方便建模和求解，需要对现实问题进行一些抽象和简化.现对本文研究的多车型配送车辆调度问题作如下描述：
1）从一个配送中心向多个客户送货，配送中心供应的货物能够满足所有客户的需求；
2）各个客户需求的货物均可以混装，单一客户的货物需求量不超过配送车辆的最大载重量，每个客户的送货要求必须满足，且仅能由一辆车完成，不允许分批配送；
3）配送车辆按载重量分类，每种车型的最大载重量一定且不允许超载，每种车型
的一次配送最大行驶距离一定，不允许超过.配送车辆均由配送中心出发，向一些客户提供配送服务，最后返回配送中心；
4）配送中心与客户之间及客户相互之间的最短距离已知且固定.
在满足上述条件下，我们要求运输成本最小.
2.构建数学模型
现有一个有向图G=（V，E），其中V={0，1，…，N}有N 1个顶点，E={（i，j）|i，j∈V，i≠j}表示弧集，顶点0表示配送中心，剩余的顶点集V′=V＼{0}表示N个配送点，为构建多车型最小费用车辆路径问题数学模型，定义以下参数：
gi： 配送点i的需求量；
φ={1，2，…，L}为车辆类型的集合，类型总数为L；
Kl：l车型的数量；
φl：车型l的车辆数集，φl={1，2，…，Kl}；
dij： 两个节点间的最短距离，i，j∈V；
Ql： 车型l的装载能力，Q0l表示车型l的空重；
cl： l型车每公里每吨的载重费用，单位：元/吨·公里；
clkij： l型车的第k辆从第i点到第j点的费用，与距离和载重有关：
clkij=dijclrlkij（i，j）∈E；l∈φ；k∈φl；
rlkij： l型车的第k辆从第i点到第j点车辆的重量；
xlkij=1 l型车的第k辆从第i点行驶到第j点0 否则
式（1）表示目标函数，即总配送成本最小；
式（2）保证车辆都是从配送中心出发，最后回到配送中心；
式（3）表示进入每个货物需求点的车辆卸载后会离开；
式（4）、（5）确保每个货物需求点只能被一辆车服务一次；
式（6）表示车辆承载的货物量之和不得大于车辆的容量；
式（7）是递推车辆行驶路径的总车质量；
式（8）是车辆回到配送中心时车辆的重量；
式（9）是不超过车辆的装载能力；
式（10）是经过某一配送点时车辆重量不能小于空车重量；
式（11）是l型车的第k辆从第i点到第j点的费用计算公式.
3.算法过程
在多车型低耗车辆路径问题解决过程中，本文采用爬山算法作为求解的主要算法.爬山算法是一种局部择优的方法，它采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策.该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解.属于人工智能算法的一种.爬山算法结构比较简单，在某些情况下，整体效率还是很好的.但它的主要缺点是有时会陷入局部最优解，而不一定能搜索到全局最优解.但由于它求解时可以把复杂问题简单化，且解的结果与最优解比较接近，所以在很多领域中都有着广泛的应用.
爬山算法的基本步骤如下：
第一步：输入多车型低耗车辆路径问题，包括配送中心、顾客点之间的坐标，配送
点需求，车型参数（载重能力、空重、不同车型固定成本）等.任意选定一个初始解x0，记录当前最优解为xbest，且令xbest=x0，令U（xbest）代表xbest的鄰域.
第二步：从xbest的邻域U（xbest）中按照某一规则选出一个解xnow，转到第三步；
若当U（xbest）=φ时，或满足其他停止运算的规则时，转到第四步；
第三步：计算xnow的目标函数值minZ1，若xnow的目标函数值minZ1小于xbest的目标函数值minZ，则xbest=xnow，minZ=minZ1，U=U（xbest），转到第二步；否则 U=U-xnow，转到第二步；
第四步：输出计算结果，停止.
在爬山算法中，第一步的初始解可以采用随机方法产生，也可以用一些经验方法或者采用其他算法得到初始解.第二步中在U（xbest）中选取xnow的规则也可以采用随机选取的规则.
4.实验计算和结果分析
实例：设配送中心（0，0）和16 个客户配送点分布及需求情况，具体数据见表1，假设该配送中心有3种车型，见表2.根据以上的爬山算法，我们应用Lingo语言来求解，获得费用最少的行驶路径，见表3，此时费用为3654.40元.
5.结 论
总的来说，对于复杂的VRP，如果仅凭决策者的经验，是很难在较短时间内作出一个合理的运输路径规划的，本文利用优化模型，采用爬山算法，再通过Lingo自动搜索得到费用最少的最优路径和车辆调度数.最终结果是比较令人满意的.
【参考文献】
[1]杨浩雄，胡静，何明珂.配送中多车场多任务多车型车辆调度研究[J].计算机工程与应用，2013，49（10）.
[2]钱艳婷，王鹏涛，魏国利.动态车辆路径问题的算法研究[J].天津理工大学学报，2010，26（6）.
[3]郭海湘，杨娟，等.煤矿物资多车型配送的改进遗传算法求解[J].运筹与管理，2011，20（2）.
【关键词】车辆调度；物流配送；多车型
【中图分类号】U492.2 【文献标识码】A
配送车辆调度问题是运筹学和组合优化领域的热点问题.多车型配送车辆调度问题是配送车辆调度问题的一个分支，一般情况下，配送企业为了适应配送商品种类繁多、性质各异、客户要求各不相同的情况，往往配置多种类型的配送车辆，以提高车辆的满载率，降低配送成本.可见，研究多车型配送车辆调度问题具有重要的理论和现实意义.
本文在现有研究成果的基础上，建立了多车型配送车辆调度问题的基于直观描述的数学模型，考虑的目标函数和约束条件比较接近实际，决策变量、目标函数和约束条件的表示较为自然、直观和易于理解.
1.对多车型配送车辆调度问题的描述
现实中的多车型配送车辆调度问题十分复杂，为了方便建模和求解，需要对现实问题进行一些抽象和简化.现对本文研究的多车型配送车辆调度问题作如下描述：
1）从一个配送中心向多个客户送货，配送中心供应的货物能够满足所有客户的需求；
2）各个客户需求的货物均可以混装，单一客户的货物需求量不超过配送车辆的最大载重量，每个客户的送货要求必须满足，且仅能由一辆车完成，不允许分批配送；
3）配送车辆按载重量分类，每种车型的最大载重量一定且不允许超载，每种车型
的一次配送最大行驶距离一定，不允许超过.配送车辆均由配送中心出发，向一些客户提供配送服务，最后返回配送中心；
4）配送中心与客户之间及客户相互之间的最短距离已知且固定.
在满足上述条件下，我们要求运输成本最小.
2.构建数学模型
现有一个有向图G=（V，E），其中V={0，1，…，N}有N 1个顶点，E={（i，j）|i，j∈V，i≠j}表示弧集，顶点0表示配送中心，剩余的顶点集V′=V＼{0}表示N个配送点，为构建多车型最小费用车辆路径问题数学模型，定义以下参数：
gi： 配送点i的需求量；
φ={1，2，…，L}为车辆类型的集合，类型总数为L；
Kl：l车型的数量；
φl：车型l的车辆数集，φl={1，2，…，Kl}；
dij： 两个节点间的最短距离，i，j∈V；
Ql： 车型l的装载能力，Q0l表示车型l的空重；
cl： l型车每公里每吨的载重费用，单位：元/吨·公里；
clkij： l型车的第k辆从第i点到第j点的费用，与距离和载重有关：
clkij=dijclrlkij（i，j）∈E；l∈φ；k∈φl；
rlkij： l型车的第k辆从第i点到第j点车辆的重量；
xlkij=1 l型车的第k辆从第i点行驶到第j点0 否则
式（1）表示目标函数，即总配送成本最小；
式（2）保证车辆都是从配送中心出发，最后回到配送中心；
式（3）表示进入每个货物需求点的车辆卸载后会离开；
式（4）、（5）确保每个货物需求点只能被一辆车服务一次；
式（6）表示车辆承载的货物量之和不得大于车辆的容量；
式（7）是递推车辆行驶路径的总车质量；
式（8）是车辆回到配送中心时车辆的重量；
式（9）是不超过车辆的装载能力；
式（10）是经过某一配送点时车辆重量不能小于空车重量；
式（11）是l型车的第k辆从第i点到第j点的费用计算公式.
3.算法过程
在多车型低耗车辆路径问题解决过程中，本文采用爬山算法作为求解的主要算法.爬山算法是一种局部择优的方法，它采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策.该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解.属于人工智能算法的一种.爬山算法结构比较简单，在某些情况下，整体效率还是很好的.但它的主要缺点是有时会陷入局部最优解，而不一定能搜索到全局最优解.但由于它求解时可以把复杂问题简单化，且解的结果与最优解比较接近，所以在很多领域中都有着广泛的应用.
爬山算法的基本步骤如下：
第一步：输入多车型低耗车辆路径问题，包括配送中心、顾客点之间的坐标，配送
点需求，车型参数（载重能力、空重、不同车型固定成本）等.任意选定一个初始解x0，记录当前最优解为xbest，且令xbest=x0，令U（xbest）代表xbest的鄰域.
第二步：从xbest的邻域U（xbest）中按照某一规则选出一个解xnow，转到第三步；
若当U（xbest）=φ时，或满足其他停止运算的规则时，转到第四步；
第三步：计算xnow的目标函数值minZ1，若xnow的目标函数值minZ1小于xbest的目标函数值minZ，则xbest=xnow，minZ=minZ1，U=U（xbest），转到第二步；否则 U=U-xnow，转到第二步；
第四步：输出计算结果，停止.
在爬山算法中，第一步的初始解可以采用随机方法产生，也可以用一些经验方法或者采用其他算法得到初始解.第二步中在U（xbest）中选取xnow的规则也可以采用随机选取的规则.
4.实验计算和结果分析
实例：设配送中心（0，0）和16 个客户配送点分布及需求情况，具体数据见表1，假设该配送中心有3种车型，见表2.根据以上的爬山算法，我们应用Lingo语言来求解，获得费用最少的行驶路径，见表3，此时费用为3654.40元.
5.结 论
总的来说，对于复杂的VRP，如果仅凭决策者的经验，是很难在较短时间内作出一个合理的运输路径规划的，本文利用优化模型，采用爬山算法，再通过Lingo自动搜索得到费用最少的最优路径和车辆调度数.最终结果是比较令人满意的.
【参考文献】
[1]杨浩雄，胡静，何明珂.配送中多车场多任务多车型车辆调度研究[J].计算机工程与应用，2013，49（10）.
[2]钱艳婷，王鹏涛，魏国利.动态车辆路径问题的算法研究[J].天津理工大学学报，2010，26（6）.
[3]郭海湘，杨娟，等.煤矿物资多车型配送的改进遗传算法求解[J].运筹与管理，2011，20（2）.