论文部分内容阅读
摘要：伴随着电子商务的发展，货车分配作业关系到整个物流的系统运作，其作用相当重要。通过对货车分配的分析，把货车的分配转化为图染色，构造货车分配问题的图染色模型，并引入算法来确定货物使用货车的时间相冲突集合，根据“先到先服务”的规则给出了货车分配的顶点序列染色算法，为电子商务时代的物流配送提供了一种全新的物流分配方式。
关键词：电子商务；物流；物流配送；图论；图染色
中图分类号：TP393文献标识码：A文章编号：1009-3044(2011)16-3936-02
1 物流配送面临的问题
物流一词源于二战间美军后勤工程，其本义就是后勤，信息时代的物流是指为了符合顾客的条件从生产地到销售地的物质、服务、和信息流通过程。配送物流是近年来的一个较新的行业，它伴随着电子商务、Internet网络和人们在线网络购物习惯改变所产生的现代服务业。在城市物流配送过程中，交通运输和车辆配送的费用问题一直是物流的一个瓶颈问题直接影响到效益。国外的现代物流业起步比较早，在车辆调度方面的技术比较合理而我国起步就比较晚相对于国的外车辆调度和货物分发技术方面都比较薄弱，大多数物流公司还处于凭经验进行调度的阶段。随着网络商城的发展、电子商务和电话购物等业态的发展，物流配送问题已经是电子商务的一热点话题，然而物流配送还面临着众多问题，如：城市交通拥堵、客户订单数量巨增、客户地点流动、客户收取货时间随机、配送车辆繁多等等问题，造成物流运输管理难度大、车辆的有效利用率低、职工工作强度提升、成本也随之日益提高、从而迫使盈利水平下降等难题。货物车辆分配问题已经是物流配送的一个核心问题，高效的货物车辆分配可以提高物流配送的服务质量，同时也可以极大的提高盈利水平。因此研究货物车辆分配已经是一个非常急迫的问题，然而图染色思想在资源最大利用率和互不相容问题解决方面有着自己独特的优势，本文就用图的染色思想去解决物流配送中的一些问题。
2 一种货物车辆分配的图染色模型
2.1 货物车辆分配的系统分析
物流配送货物车辆根据所能车辆的车型大小分为大中和小型车辆，货物车辆分配是指根据车辆的属性给每件物品分配一辆特定的货车， 其中包括开始使用货车的出发时刻以及结束使用该货车的时刻。在一个时间段内的不同时期内由于离开分发站和到达分发站的货车种类、货车时间和货车数目不同, 最终确定物流货车的种类和时间也就不相同。实际对货车进行分配使用时必须满足下列约束条件:
1) 每一件物品不能同时被分配到多辆货车。
2) 同一个货车在同一时间段内不能被分配到多条路线。
3) 物流中转站应相满足车站衔接以和过站时间衔接要求，具体包括从开始使用货车到货车使用结束期间的时间间隔不能小于货车完成一次正常过站流程所需的最短时间以确保货物中转的顺利完成。
4) 货物车辆与货物装载应该相互匹配，即大型货车可以装载大型货物和重型货物，小型货车装载小型货物和轻量级货物，根据货车的快慢速度和货物的紧急程度选择合适的车辆进行配送。
2.2 一种货物装车分配的图染色模型
将基于图染色的货物装车分配结果转化为图染色模型，图染色模型可以由以下二元式组成:
G(V,E)其中:
V={vi|待分配货物的所有车辆i};
E={(vi,vj)货物车辆分配中相冲突货物};
货物车辆分配图中, 顶点V 表示需要分配货物车辆的所有车辆集合, V={vj|i=1,2,…,n}; 边代表装载货物时互冲突的货物集合, E={(vi,vj)|i=1,2,…,m;j=1,2,…,n;i≠j。图的染色是指对冲突图中的顶点进行染色, 在满足一定条件下, 使得任意两个相邻顶点不具有相同的颜色，使所需要的颜色数, 即使用的货车数最少。在货车分配中，货车作为颜色的集合C={Ck|k1,2,…,K}, 按照约束关系, 货物配送与货车的匹配关系可以用映射函数表示为: φ:V->C,?坌Vi,Vj, ∈V:{ Vi,Vj }∈E, 则φ(Vi) ≠φ(Vj)。满足:
1) 同一时间内每辆货车最多只能占用一条路线;
2) 每件货物只能被分配给一辆货车装载,并且每件货物被执行开始就不能中途停止直至使用完毕;
3) 每件货物和被分配到的货车应相互匹配。
3 解决物流配送的图着色问题算法
图的染色问题近年来在国内外都是一个研究热点，尤其在有关生产调度领域存在着广阔的应用背景，在课表编排频率分配、资源分配以及货物存储方面都得到了很好的应用, 下面给出了物流货车分配的顶点序列染色算法。
3.1 一些有关图染色的符号说明
在给出货车分配的图染色模型算法之前, 首先给出在算法中用到的一些符号以及简要说明。
Δ(v)表示顶点的度数, 是图G 中和顶点v 相关联的所有边的集合数目。
N(v)表示顶点v 的邻集N(v):G中和顶点v 相邻的顶点的集合。
Uf(v)表示顶点v 的禁色集Uf(v) :顶点v不可使用的颜色的集合, 该集合由顶点v 的邻集N(v)中已染色顶点所使用的颜色与相应的约束条件共同决定最终形成的。
Lf(v)表示顶点v的禁色数lf(v) 禁止顶点v 使用的颜色的数目(lf(v)=|Uf(v)|)。
Cv(G)表示顶点v 染色时, G 中已被染色顶点所用颜色的集合。
R(v)表示顶点v 染色时, 顶点v可选用的已用颜色的集合（R(v)=Cv(G)-Uf(v)）。
r(v)表示顶点v 染色时, 顶点v 可选用的已用颜色的数目(r(v)=R(v))。
3.2 算法步骤
结合货物车辆分配中的实际情况, 给出基于货物车辆分配的顶点序列染色算法，执行步骤如下:
第一步：依据划分时间片算法计算出使用货物车辆时间冲突的所有货物集合E。
第二步：将要被分配的货物按其时间冲突情况做出二元图G(V,E)。
第三步：把图中顶点的度数Δ(v)从大到小进行降序排序。
第四步：为度数最大的顶点分配第一组颜色, 如果度数相同则选禁色数lf(v)最大的顶点。
第五步：继续扫描剩余货物, 如果它们与刚被分配过的货物是相邻接的, 其度数减一。 对剩余的未染色的货物按其度数继续进行下一轮降序排列，如果度数相同, 则选择一个禁色数lf(v); 如果不止一个, 选其中度数最大的一个。
第六步：将选出的货物染以可选用的色号尽可能小的颜色(若R(v) ≠?堙, 对R(v)中的颜色优先);
第七步：如果所有的货物都已被染色就可以停止反之继续执行第五步。
3.3 算法评析
算法优劣的一个评判标准就是算法的复杂性，本文给出的算法复杂性集中在第三步)～第七步, 假设待分配货车的货物数量为n, 货车数量为k。算法在执行第三步中对货物按顶点度数由大到小整理的复杂性为O(n2) , 算法在执行第四步～ 第七步中为每件货物分配相匹配的车辆的复杂性为O(k2)，因此总体完成整个货物车辆分配的算法复杂性为O(n2k2)。
4 结束语
目前，我国大部分货物配送运输管理中的货物车分配调度仍然是人工操纵, 严重影响物流的流通效率和物流配送的经济效益，不符合电子商务时代的物流配送需求，这篇文章采用图染色的思想构造了货物车辆分配计划的图染色模型, 根据顶点序列染色的启发式算法, 将其应用到实际物流运行管理的计算分析系统中, 为物流分配计划分析计算提供了一种全新的途径，充分的利用了电子商务时代以信息迅速处理和传递为目标的特点，有助于提高物流分配的速度从而提高经济效益和服务质量，为电子商务时代物流配送提供了一种新的调试方式。
参考文献：
[1] 孙明贵,潘留栓.物流管理学[M].北京:北京大学出版社,2002.
[2] 刘云翔.基于城市道路网的最短路径分析解决方案[J].小型微型计算机系统,2003(7):23-26.
[3] 邓慧超,蓝庆新.发达国家和地区物流配送方式的比较与借鉴[J].物流技术,2003(3).
[4] 王淑琴,陈峻.长三角物流园区一体化规划探讨[J].城市规划汇刊,2004(3):54-56
[5] RonaldH.Baollon.企业物流管理一供应链的规划、组织和控制[M].王晓东,胡瑞娟,译.机械工业出版社,2002.
[6] 张忠辅,陈祥恩,李敬文.关于图的邻点可区别全染色[J].中国科学(A辑),2004,34(5)574-583.
[7] 李敬文,徐保根,李沐春,等.Pm Cn的点可区别边色数[J].山东大学学报,2008,43(8):24-30.
[8] Zhang Zhong-fu,Liu Liu-zhong,Wang Jian-fang.Adjacent strong Edge coloring ofgraphs[J].Applide Mathematics Letters,2002,15(3):623-626
[9] Zhang Zhong-fu,Chen Xian-gen,Li Jingwen,et al.Vertex-distinguishing total coloring of graphs[J].Science in China(Series A:Mathematics),2006,10(2).
关键词：电子商务；物流；物流配送；图论；图染色
中图分类号：TP393文献标识码：A文章编号：1009-3044(2011)16-3936-02
1 物流配送面临的问题
物流一词源于二战间美军后勤工程，其本义就是后勤，信息时代的物流是指为了符合顾客的条件从生产地到销售地的物质、服务、和信息流通过程。配送物流是近年来的一个较新的行业，它伴随着电子商务、Internet网络和人们在线网络购物习惯改变所产生的现代服务业。在城市物流配送过程中，交通运输和车辆配送的费用问题一直是物流的一个瓶颈问题直接影响到效益。国外的现代物流业起步比较早，在车辆调度方面的技术比较合理而我国起步就比较晚相对于国的外车辆调度和货物分发技术方面都比较薄弱，大多数物流公司还处于凭经验进行调度的阶段。随着网络商城的发展、电子商务和电话购物等业态的发展，物流配送问题已经是电子商务的一热点话题，然而物流配送还面临着众多问题，如：城市交通拥堵、客户订单数量巨增、客户地点流动、客户收取货时间随机、配送车辆繁多等等问题，造成物流运输管理难度大、车辆的有效利用率低、职工工作强度提升、成本也随之日益提高、从而迫使盈利水平下降等难题。货物车辆分配问题已经是物流配送的一个核心问题，高效的货物车辆分配可以提高物流配送的服务质量，同时也可以极大的提高盈利水平。因此研究货物车辆分配已经是一个非常急迫的问题，然而图染色思想在资源最大利用率和互不相容问题解决方面有着自己独特的优势，本文就用图的染色思想去解决物流配送中的一些问题。
2 一种货物车辆分配的图染色模型
2.1 货物车辆分配的系统分析
物流配送货物车辆根据所能车辆的车型大小分为大中和小型车辆，货物车辆分配是指根据车辆的属性给每件物品分配一辆特定的货车， 其中包括开始使用货车的出发时刻以及结束使用该货车的时刻。在一个时间段内的不同时期内由于离开分发站和到达分发站的货车种类、货车时间和货车数目不同, 最终确定物流货车的种类和时间也就不相同。实际对货车进行分配使用时必须满足下列约束条件:
1) 每一件物品不能同时被分配到多辆货车。
2) 同一个货车在同一时间段内不能被分配到多条路线。
3) 物流中转站应相满足车站衔接以和过站时间衔接要求，具体包括从开始使用货车到货车使用结束期间的时间间隔不能小于货车完成一次正常过站流程所需的最短时间以确保货物中转的顺利完成。
4) 货物车辆与货物装载应该相互匹配，即大型货车可以装载大型货物和重型货物，小型货车装载小型货物和轻量级货物，根据货车的快慢速度和货物的紧急程度选择合适的车辆进行配送。
2.2 一种货物装车分配的图染色模型
将基于图染色的货物装车分配结果转化为图染色模型，图染色模型可以由以下二元式组成:
G(V,E)其中:
V={vi|待分配货物的所有车辆i};
E={(vi,vj)货物车辆分配中相冲突货物};
货物车辆分配图中, 顶点V 表示需要分配货物车辆的所有车辆集合, V={vj|i=1,2,…,n}; 边代表装载货物时互冲突的货物集合, E={(vi,vj)|i=1,2,…,m;j=1,2,…,n;i≠j。图的染色是指对冲突图中的顶点进行染色, 在满足一定条件下, 使得任意两个相邻顶点不具有相同的颜色，使所需要的颜色数, 即使用的货车数最少。在货车分配中，货车作为颜色的集合C={Ck|k1,2,…,K}, 按照约束关系, 货物配送与货车的匹配关系可以用映射函数表示为: φ:V->C,?坌Vi,Vj, ∈V:{ Vi,Vj }∈E, 则φ(Vi) ≠φ(Vj)。满足:
1) 同一时间内每辆货车最多只能占用一条路线;
2) 每件货物只能被分配给一辆货车装载,并且每件货物被执行开始就不能中途停止直至使用完毕;
3) 每件货物和被分配到的货车应相互匹配。
3 解决物流配送的图着色问题算法
图的染色问题近年来在国内外都是一个研究热点，尤其在有关生产调度领域存在着广阔的应用背景，在课表编排频率分配、资源分配以及货物存储方面都得到了很好的应用, 下面给出了物流货车分配的顶点序列染色算法。
3.1 一些有关图染色的符号说明
在给出货车分配的图染色模型算法之前, 首先给出在算法中用到的一些符号以及简要说明。
Δ(v)表示顶点的度数, 是图G 中和顶点v 相关联的所有边的集合数目。
N(v)表示顶点v 的邻集N(v):G中和顶点v 相邻的顶点的集合。
Uf(v)表示顶点v 的禁色集Uf(v) :顶点v不可使用的颜色的集合, 该集合由顶点v 的邻集N(v)中已染色顶点所使用的颜色与相应的约束条件共同决定最终形成的。
Lf(v)表示顶点v的禁色数lf(v) 禁止顶点v 使用的颜色的数目(lf(v)=|Uf(v)|)。
Cv(G)表示顶点v 染色时, G 中已被染色顶点所用颜色的集合。
R(v)表示顶点v 染色时, 顶点v可选用的已用颜色的集合（R(v)=Cv(G)-Uf(v)）。
r(v)表示顶点v 染色时, 顶点v 可选用的已用颜色的数目(r(v)=R(v))。
3.2 算法步骤
结合货物车辆分配中的实际情况, 给出基于货物车辆分配的顶点序列染色算法，执行步骤如下:
第一步：依据划分时间片算法计算出使用货物车辆时间冲突的所有货物集合E。
第二步：将要被分配的货物按其时间冲突情况做出二元图G(V,E)。
第三步：把图中顶点的度数Δ(v)从大到小进行降序排序。
第四步：为度数最大的顶点分配第一组颜色, 如果度数相同则选禁色数lf(v)最大的顶点。
第五步：继续扫描剩余货物, 如果它们与刚被分配过的货物是相邻接的, 其度数减一。 对剩余的未染色的货物按其度数继续进行下一轮降序排列，如果度数相同, 则选择一个禁色数lf(v); 如果不止一个, 选其中度数最大的一个。
第六步：将选出的货物染以可选用的色号尽可能小的颜色(若R(v) ≠?堙, 对R(v)中的颜色优先);
第七步：如果所有的货物都已被染色就可以停止反之继续执行第五步。
3.3 算法评析
算法优劣的一个评判标准就是算法的复杂性，本文给出的算法复杂性集中在第三步)～第七步, 假设待分配货车的货物数量为n, 货车数量为k。算法在执行第三步中对货物按顶点度数由大到小整理的复杂性为O(n2) , 算法在执行第四步～ 第七步中为每件货物分配相匹配的车辆的复杂性为O(k2)，因此总体完成整个货物车辆分配的算法复杂性为O(n2k2)。
4 结束语
目前，我国大部分货物配送运输管理中的货物车分配调度仍然是人工操纵, 严重影响物流的流通效率和物流配送的经济效益，不符合电子商务时代的物流配送需求，这篇文章采用图染色的思想构造了货物车辆分配计划的图染色模型, 根据顶点序列染色的启发式算法, 将其应用到实际物流运行管理的计算分析系统中, 为物流分配计划分析计算提供了一种全新的途径，充分的利用了电子商务时代以信息迅速处理和传递为目标的特点，有助于提高物流分配的速度从而提高经济效益和服务质量，为电子商务时代物流配送提供了一种新的调试方式。
参考文献：
[1] 孙明贵,潘留栓.物流管理学[M].北京:北京大学出版社,2002.
[2] 刘云翔.基于城市道路网的最短路径分析解决方案[J].小型微型计算机系统,2003(7):23-26.
[3] 邓慧超,蓝庆新.发达国家和地区物流配送方式的比较与借鉴[J].物流技术,2003(3).
[4] 王淑琴,陈峻.长三角物流园区一体化规划探讨[J].城市规划汇刊,2004(3):54-56
[5] RonaldH.Baollon.企业物流管理一供应链的规划、组织和控制[M].王晓东,胡瑞娟,译.机械工业出版社,2002.
[6] 张忠辅,陈祥恩,李敬文.关于图的邻点可区别全染色[J].中国科学(A辑),2004,34(5)574-583.
[7] 李敬文,徐保根,李沐春,等.Pm Cn的点可区别边色数[J].山东大学学报,2008,43(8):24-30.
[8] Zhang Zhong-fu,Liu Liu-zhong,Wang Jian-fang.Adjacent strong Edge coloring ofgraphs[J].Applide Mathematics Letters,2002,15(3):623-626
[9] Zhang Zhong-fu,Chen Xian-gen,Li Jingwen,et al.Vertex-distinguishing total coloring of graphs[J].Science in China(Series A:Mathematics),2006,10(2).