• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Operations Research >An exact algorithm for the capacitated arc routing problem with deadheading demand
【24h】

An exact algorithm for the capacitated arc routing problem with deadheading demand

机译：具有空载需求的电容弧布线问题的精确算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The capacitated arc routing problem (CARP) consists of a set of vehicles routs such that each vehicle services starting from the depot and after servicing a subset of edges returns to the depot, to total demand serviced by the vehicle does not exceed a predefined level, and the sum of dead locking costs are minimized. The main lower bound and exact algorithms are based on cutting planes and transformations in to a capacitated vehicle routing problem. Some of the best exact algorithms employ column generation and cut-and-column generation techniques, or a set partitioning model of the CARP. This paper studies an extension of CARP called capacitated arc routing problem with deadheading demand (CARPDD) Kirlik and Sipahioglu (Ref. 1). CARPDD works with a travel demand in addition to the service demand. The total capacity consumption of a vehicle is the sum of demands of the serviced edges, plus the sum of travel demands of the deadheaded edges of its route and the feasibility of the CARPDD also depends on their routes. The CARPDD is NP-hard as it reduces to the CARP when the travel demands are zero. (36 refs.).
机译：电容弧布线问题（CARP）由一组车辆溃败组成，这样，从车厂开始并在维修了一部分边沿后返回车厂的每辆车服务，到车辆所服务的总需求不超过预定水平，并且将死锁成本的总和最小化。主要的下限和精确算法基于切割平面并转换为容量较大的车辆路径问题。一些最精确的算法使用列生成和剪切列生成技术，或CARP的设置分区模型。本文研究了带有无头要求的电容电弧路由问题（CARPDD）Kirlik和Sipahioglu的CARP扩展（参考文献1）。除服务需求外，CARPDD还可以满足旅行需求。车辆的总容量消耗是服务边缘的需求之和，加上其路线无头边缘的行驶需求之和，而CARPDD的可行性也取决于其路线。 CARPDD是NP-hard的，因为当旅行需求为零时，它会减少为CARP。 （36参考。）

著录项

  • 来源
    《Operations Research》 |2014年第6期|477-478|共2页
  • 作者

    Enrico Bartolini; Jean-Francois Cordeau; Gilbert Laporte;

  • 作者单位

    HEC Montreal, and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Quebec H3T 2A7, Canada;

    HEC Montreal, and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Quebec H3T 2A7, Canada;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号