物流管理中的图分割问题.pdf

第38卷 第2期 应 用 数 学 学 报 Vo1．38No．2 2015年 3月 ACTAMATHEMATICAEAPPLICATAESINICA March，2015 物流管理中的图分割问题 陈智勤 李成进 张圣贵 (福建师范大学数学与计算机科学学院，福州350007) (E-mail：zqchen@fjnu．edu．cn) 摘 要 本文将利用图分割对物流管理中出现的问题进行建模，并利用一种新的方法来对这个 含矩阵秩约束的模型进行求解．最后，给出了初步的数值结果。 关键词 物流；图分割；矩阵秩约束；近似函数 MR(2000)主题分类 65K05；90C30 中图分类 O221．2 1 引言 现代，许多民营物流企业都是从一个规模很小的运输公司发展起来的．最初的时 候，这些运输公司利用一、两部车经营着一些固定线路的运输；接着，为了提高单车的 装载率，扩大经营的规模，运输公司会在一个城市的各个位置设立 自已的接送货点； 最后，随着公司业务的进一步扩大，每个接送货点都可能成为一个办事处．在一个城市 中，物流公司的布局是这样的一种状况，对于一个省份而言，各个城市或地区的布局也 是这样，就是物流公司会在各城市成立 自己的分公司，或是与其它公司合作的分公司． 本文只对一个城市内部的各办事处的布局进行考虑，至于其它情况，则可以类似地 进行推广．为了提升对各个办事处的管理与控制，提高车辆的调度效率，加强运输订单 资源的灵活分配，强化市内接送货车辆的资源共享，物流公司通常会将一个城市内部的 多个办事处划分为两个分公司或多个分公司进行分别管理．这种多个分公司的运营模 式的意义是：首先，可以减小整个公司的管理幅度；其次，在一个分公司的办事处间容 易落实车辆与订单的资源共享，即在分公司内部可进行国车辆的统一调度，因此车辆送 货的同时往往可以顺道完成从客户处接货的任务．虽然，上述的第二点意义也可通过把 同一城市内所有办事处整合为一个分公司的方式来实现，但实践证明管理一个包含太 多办事处的公司是非常不易的，经常会出现管理失控的情况．例如，各办事处的负责人 本文 2013年 7月 9日收到．2013年 l1月 5日收到修改稿． 国家自然科学青年基金 ，福建省教育厅B类 (JB12040)以及非线性分析及其应用 (IRTL1206)资 助项 目． 2期 陈智勤，李成进，张圣贵：物流管理 中的图分割问题 357 通常不会以整个公司的利益最大化做为 目标来管理 日常业务，从而导致整个公司的利 益受损．具体地，可以打个比方来说明，假设A办事处的一运单资源若与B办事处的运 单资源整合拼车是公司整体成本的最优选择，但A办事处的负责人可能基于与C办事 处负责人的关系好的原因而选择与 C办事处的运单进行拼车，这就造成了不必要的损 失．若按多个分公司共同运营的话，我们可以将A、B两办事处划分在同一分公司， 而 C办事处分在另一个不同分公司，这样的话 A，C两个办事处的整合拼车就会存在一 个费用结算问题，而这个额外费用就可以当作对A，C所在分公司不利的考核指标． 总之，现代的物流企业，为了提高管理成效，一般都会实旌一系列的绩效管理措 施，在提高运营利润的同时，尽力减少不同分公司之间在业务合作方面产生额外的成本 费用．也就是说，这些企业往往会在确定各个分公司所含办事处个数等前提条件下，对 所有办事处进行划分以减少总体的合作成本．因此，如何对办事处进行合理的分公司划 分，使得各办事处间在合作便利的前提下所产生的额外费用最少就是我们 目前要研究 的问题．一般来说一个城市内的多个办事处划分为两个分公司进行分别管理的情况较 多，因此，在这里我们只讨论两个分公司的情况．当然，这是一个很难解决的问题．因 为在这个问题中，既要考虑现实中地域远近的问题，又要考虑尽可能减少两个分公司之 间因接送货而产生的费用问题． 从建模的角度上看，若把一个城市看成是一张图，把各个办事处看成为图上的节 点，在任意两个办事处之间都用一条无向边相连，并在每条边上定义权重 (此权重取为 当两个