试题详情
简答题 某物流中心A用一辆厢式货车将货物配送给四个超市B，C，D，E，物流中心到超市以及超市与超市之间的距离如图所示，试确定最佳的循环式行驶路线。
  • 确定距离矩阵。根据题图所给出的各节点间的距离，确定距离矩阵，如表所示。

    确定每一个节点到其它所有节点的距离之和。例，节点A到其它四个节点的距离分别为9，10，10，6，那么和为35。详见表最后一行。
    确定一个初选的循环路线。按照距离之和由大到小依次选取三个节点（A，D，C）组成循环路线，即A—D—C—A。
    确定插入其它节点。在不在初选循环路线的剩余节点中，选择距离之和最大者所对应的节点作为插入点，即B点。
    确定插入位置。从上述描述可知，B点可能插入的位置为AD，DC和CA之间，即。具体的位置为插入B点以后使循环回路的里程增加最少。里程增量的计算为：
    δAD=IAB+IBD-IAD=9+12-10=11
    δDC=IDB+IBC-IDC=12+7-12=7 δ
    CA=ICB+IBA-ICA=7+9-10=6
    所以，B点应该插入C与A之间。则此时的循环路线为：A—D—C—B—A。
    将剩余的不在循环路线上的节点依照上面的方法插入循环路线中，最终的循环路线为A—E—D—C—B—A。

  • 关注下方微信公众号，在线模考后查看

热门试题