Design and analysis of efficient algorithms for location-routing problems

现代工业运作的效率要求以最佳方式配置资源。这导致了关于资源分配的业务研究的广泛工作，重点是最优或接近最优的规划。我建议研究一个称为定位路线问题的组合问题的算法方面。选址-布线研究领域包括经典的设施选址和布线领域。服务提供商的位置往往受到运输成本的影响。显然，单独处理这一问题往往会导致次优算法。有许多实际的工业问题可以从这一领域的理论结果中受益。 我们将首先在设施选址和车辆路线领域的研究基础上再接再厉。取得了重大进展，但在这些领域仍然存在许多问题。特别关注的是结构良好的图类，如部分k-树。这项研究的长期目标仍然是将选址规划与旅游规划方面结合起来。对移动传感器网络的另一个关注提出了新的组合问题，这是由网络的自组织性质引起的。

Efficiency in modern industrial operations requires that resources be deployed in optimal manner. This has resulted in extensive work in operations research on resource allocation with a focus optimal or near optimal planning. I propose to study algorithmic aspects of a combinatorial problem called location routing problem. Location-routing research area encompasses the classical facility location and routing areas. The location of service providers is often influenced by transport costs. Clearly, dealing this problem separately, will often result in suboptimal algorithm. There are a host pf practical industrial problems which can benefit from the theoretical results in this area. We will first build on our research in the areas of facility location and vehicle routing. Significant progress has been made, but still many problems remain in these areas. A particular focus will be on well structured classes of graphs such as partial k-trees. The long term objective of this research remains the goal of integrating the location planning with tour planning aspects taken into account. An additional focus on mobile sensor networks raises novel combinatorial questions arising from the ad-hoc nature of network.