基于梯森分割的城市物流配送路线优化选择  

Optimal Choosing for Urban Logistics Distribution Route Based on Thiessen Tessellation

作　　者：严洁云[1] 肖桂荣[1] 石松[1] 毛政元[1] 

机构地区：[1]福州大学福建省空间信息工程研究中心数据挖掘与信息共享教育部重点实验室,福州350002

出　　处：《计算机工程与应用》2005年第36期210-212,共3页Computer Engineering and Applications

基　　金：福建省教育厅科技项目"城市物流空间信息服务平台建设"(编号:JA04153)

摘　　要：物流配送车辆路径优化问题是一个典型的NP难题,也是近年来物流研究中的一个热点。文章利用先分组再排路线的思想,把城市零售商品物流配送车辆路径优化问题分解成一个分派问题和一个类似旅行商问题(TravelingSalesm an Problem,TSP)。应用空间分析中的梯森分割(Thiessen Tessellation)理论解决分派问题,同时改进用于求解TSP问题的插队算法,将其应用于对车辆巡回路线寻优问题的求解,最后,对此算法进行了应用举例。The logistics distribution Vehicle Routing Problem,a typical NP-hard problem,is a hot topic in logistics research.This paper decomposes the logistics distribution VRP of urban retail merchandise into an assignment problem and a problem similar to Traveling Salesman Problem,using the idea of Cluster First Route Second.The theory of Thiessen Tessellation in spatial analysis is applied to solve the assignment problem and an algorithm called nested queue-jumping algorithm for TSP which is advanced is used for Vehicle Routing Problem.An example for this algorithm is given at the last part.

关 键 词：物流配送 梯森分割 旅行商问题(TSP) 插队算法 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]