Design and analysis of efficient algorithms for location-routing problems

定位路由问题的有效算法的设计和分析

• 批准号: 2422-2011
• 负责人: Bhattacharya, Binay
• 金额: $ 1.75万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568244
• 关键词: Design; analysis; efficient; algorithms; location

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.

现代工业运营的效率要求以最佳方式部署资源。这导致了大量的工作，在业务研究的资源分配与重点最佳或接近最佳的规划。我建议研究算法方面的组合问题称为定位路由问题。定位-路径研究领域涵盖了经典的设施定位和路径选择领域。服务提供者的地点往往受到运输成本的影响。显然，单独处理这个问题，往往会导致次优算法。这一领域的理论成果对许多实际工业问题都有借鉴意义。 我们将首先建立在我们的研究领域的设施位置和车辆路线。在这些领域取得了重大进展，但仍存在许多问题。一个特别的重点将是结构良好的图形类，如部分k树。本研究的长期目标仍然是将位置规划与旅游规划方面考虑在内的目标。移动的传感器网络的额外重点提出了新的组合问题所产生的自组织网络的性质。