Set covering in fuel-considered vehicle routing problems

作     者：Song, Liang Chen, Haibin Gu, Hao Huang, Hejiao Du, Hongwei 

作者机构：Harbin Inst Technol Shenzhen Grad Sch Harbin Peoples R China Shenzhen Key Lab Internet Informat Collaborat Harbin Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2015年第607卷第Part3期

页      面：471-479页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [11371004, 61370216] Shenzhen Strategic Emerging Industries Program [ZDSY20120613125016389, JCYJ20120613151201451, JCYJ20130329153215152] 

主　　题：Set covering Bicriteria approximation algorithms Lower bound Total unimodularity Fuel-considered vehicle routing problems 

摘      要：The paper studies set covering in fuel-considered vehicle routing problems (FVRP). Firstly, we study the FVRP with distance constraint and time windows (FVRP-TW) whose objective is to find a set covering with the minimum cardinality, which means the number of used vehicles is minimized and hence the fuel consumption is minimized in the real logistics. We give a bicriteria approximation algorithm for this problem. Secondly, we study the set covering in the FVRP with distance constraint and constant time windows (FVRP-CTW), which has a constant number of the time windows provided by logistics companies. We give a bicriteria approximation algorithm with (2+epsilon, O(log1/epsilon)) for this problem, in which the first term is the approximation ratio on the distance constraint and the second term is the approximation ratio on the cardinality of the covering set. Thirdly, we study the set covering in general FVRP and propose a lower bound for this problem which is based on total unimodularity. Finally, we design an algorithm framework based on the lower bound for solving the set covering in general FVRP. Simulation results demonstrate the effectiveness of the algorithms for solving the set covering in FVRP-TW and general FVRP. (C) 2015 Elsevier B.V. All rights reserved.