注册 | 登录
  • 首  页
    |
  • 关于学会
    |
  • 网上入会
    |
  • 学术年会
    |
  • 学会论文
    |
  • 学会课题
    |
  • 学会报告
    |
  • 学会活动
    |
  • 产学研基地
    |
  • 特约研究员
    |
  • 资料中心
    |
学会介绍 学会章程 会员管理服务及收费办法 组织机构 学会领导 专家委员会 学会年度工作计划 学会文件 联系方式
入会须知 注册会员 理事申请表下载 会费标准及缴纳方式
关于年会 历届年会回顾 最新年会动态 最新学术年会征文 历届获奖名单 特约评委申报 关于分论坛 分论坛申请 历届分论坛
征文通知 征文提交 物流经济 物流管理 物流技术与工程 采购 供应链管理 英文文献
课题介绍 课题通知 课题计划 历年获奖课题 课题申报 课题结题 课题申报书下载 课题延期申请表下载 研究报告格式规范下载 结题报告模板下载
关于报告 中国物流发展报告 中国物流重点课题报告 中国物流学术前沿报告 中国物流园区发展报告 中国冷链物流发展报告 生产资料流通发展报告 中国采购发展报告
中国物流发展报告会 全国物流园区工作年会 物流企业财税与投融资工作会 产学研结合工作会 中国物流学术年会 日日顺创客训练营
管理办法 产学研基地动态 申请表下载 申请表提交 基地复核 产学研会议信息
管理办法 申请流程 聘任条件 申请表下载 特约研究员相关文件
学会工作动态 物流政策及评论 学术年会论文 学术年会资料 学会报告 会员通讯 领导讲话 学会文件 学会课题 其他
  • 2005年
  • 2006年
  • 2007年
  • 2008年
  • 2009年
  • 2010年
  • 2011年
  • 2012年
  • 2013年
  • 2014年
  • 2015年
  • 2016年
  • 2017年
  • 2018年
  • 2019年
  • 2020年
  • 2021年
当前位置:首页 > 资料中心 > 学术年会论文 > 英文文献 > 2019年
The generalized rollon-rolloff vehicle routing problem and savings-based algorithm
来源: 时间:2019/12/4 10:03:46 作者:
  

The generalized rollon-rolloff vehicle routing problem and savings-based algorithm

Hongqi Li a *, Xiaorong Jiana, Xinyu Changb, Yingrong Lua, c

aSchool of Transportation Science and Engineering, Beihang University. No. 37 Xueyuan Road, Haidian District, Beijing, 100191, China

bChina Academy of Transportation Sciences. No. 240 Huixinli, Chaoyang District, Beijing, 100029, China

cBeijing Key Laboratory for Cooperative Vehicle Infrastructure System and Safety Control, Beihang University. No. 37 Xueyuan Road, Haidian District, Beijing, 100191, China

 

* Corresponding author.E-mail addresses: lihongqi@buaa.edu.cn

 

 

Abstract

Taking the waste collection management as the practical background, the rollon-rolloff vehicle routing problem (RRVRP) involves tractors pulling large containers between customer locations and the disposal facility. Each used-tractor begins and ends its route at the depot. Customer demand includes emptying a full container, ordering an empty container or changing a container. The objective is to find tractor routes that feature the minimum amount of total nonproductive time. In the literature the RRVRP is formulated as the node routing problem, and the “trip” definition that is the complete transport service of a container is used. To relax some assumptions of the RRVRP to cater to practical desires, we present a variant called the generalized RRVRP (G-RRVRP). The G-RRVRP generalizes the practical background,the objective function and the demand flow, and considers specially container loading and unloading time constraints. The G-RRVRP classifies demand into loaded-container demand and cargo demand with time windows. On condition of respecting container loading/unloading time and customer time windows, the G-RRVRP can design tractor routes for the synchronous scheduling of loaded and empty containersso as to ensure the timeliness of transport service. The G-RRVRP aims to minimizethe total running cost ofused tractors, instead of the total nonproductive time of tractors adopted by the RRVRP. A mixed integer linear programming model for the G-RRVRPis proposed. The Benders decomposition algorithm involving Pareto-optimal cuts and Benders decomposition-callback implementation, and a two-stage heuristicinvolving the savings algorithm followed by a local search phase are provided. The mathematical formulation and the two-stage heuristic are tested by solving 40 small-scale instances and 20 benchmark instances. Small-scale instances can be solved directly by CPLEX through the Benders decomposition strategies to find exact solutions. The case study indicates the applicability of the G-RRVRP model and thetwo-stageheuristic to realistic-size problems abstracted from intercity linehaul systems. The computational experiments and case study indicate that the heuristic can solve various instances of the G-RRVRP such that the solution quality and the computation time are acceptable. 

Keywords: Rollon-rolloff vehicle routing problem; Generalized RRVRP;Mixed integer linear programming;Benders decomposition; Savings algorithm

 

1. Introduction

So farresearchers have put forward several kinds of vehicle routing problems (VRPs) catering to waste collection management, one of which is the rollon-rolloff vehicle routing problem (RRVRP). The basic form of the RRVRP was presented by Bodin et al. (2000). The RRVRP involves one depot for holding tractors and one disposal facility for emptying full-containers. Each used-tractor begins and ends its route at the depot. Customer demand includes emptying a full container, ordering an empty container or replacing a full container with an empty container. Tractors pull large containers between customer locations and the disposal facility. Tractorscan only move one container to serve one customer at a time (Kim et al., 2006). The objective is to find tractor routes that feature the minimum of total nonproductive time.In nonproductive time tractors run alone on arcs. 

The waste collection management is the practical background of the RRVRP. Formulating the RRVRP as the node routing problem, Bodin et al. (2000) presented the RRVRP on a directed complete graph G=(V, A). Ais the arc set. Vis the vertex set that consists of one depot, one disposal facility which is also regarded as an unlimited inventory of empty containers, and an amount of customer locations. Customer demand is classified into several types of trips served by tractors. A “trip” is defined to be the complete service of a container for a customer. Four types of trips (i.e., Type 1, Type 2, Type 3, and Type 4) are defined in the RRVRP stated by Bodin et al. (2000). For the Type 1, a full container is transported by a tractor from a customer to the disposal facility for emptying, and the emptied container is returned to the customer by the same tractor. For the Type 2, an empty container is exchanged with a full container at a customer location. For the Type 3, an empty container is brought to a customer. For the Type 4, a full container from a customer is transferred to the disposal facility. The service time of a trip includes container loading/unloading time and traveling time. The loaded container leg and the empty container leg are integrated in the first or the second type of trips. 

In the literature several variants of the RRVRP have been proposed, which are characterized by the involved service types, time windows, etc. De Meulemeester et al. (1997) solved a variant associated with the collection and delivery of skips. A tractor can carry only one skip at a time. In one skip a tractor departing from a depot transports a full container from a customer location to a disposal site. Bodin et al. (2000) solved the RRVRP throughseveral heuristics, and twenty benchmark instances ranging from 50 to 199 trips and belonging to four classes (i.e., class A, B, C, or D) were used. In each class there are five test problems. The four classes differ in the mix of Type 1, Type 2, Type 3, and Type 4 trips. The number of trips in the five test problems in each class is 50, 75, 100, 150, and 199 trips, respectively. The class A problems have a preponderance of Type 1 trips, the class B problems have about the same number of Type 1 and Type 2 trips, and the class C problems have a preponderance of Type 2 trips. All class A, class B, and class C problems have only a few Type 3 and Type 4 trips. The class D problems have about the same number of Type 1, Type 2, Type 3, and Type 4 trips. Derigs et al. (2013) combined local search and large neighborhood search to solve the twenty benchmark instances provided by Bodin et al. (2000). Wy and Kim (2013) adopted a large neighborhood search and various improvement methods to solve the RRVRP. New best-known solutions are found for seventeen instances out of the twenty benchmark instances of Bodin et al. (2000). Baldacci et al. (2006) proposed the multiple disposal facilities and multiple inventory locations RRVRP (M-RRVRP). Five types of trips are considered. A bounding procedure combining three lower bounds derived from different relaxations of the M-RRVRP formulation is provided.Wy et al. (2013) presented the RRVRP with time windows (RRVRPTW) considering multiple disposal facilities and multiple inventory locations. Hauge et al. (2014) addressed another type of the RRVRP in which four types of trips, multiple depots, multiple disposal facilities and various container types are considered. 

需要[2]积分

阅读全文

关于我们 | 媒体互动 | 站点留言 | 友情链接 | 在线投稿 | 网站地图

地 址: 北京市丰台区丽泽路16号院2号楼铭丰大厦1601(100073) 电 话:010-83775681 E-mail:CSL56@vip.163.com
Copyright 2000-2019 in 中国物流与采购联合会、中国物流学会版权所有 技术支持:中国物流与采购联合会网络事业部
中国物流与采购网:京ICP备05024070号 中国物流联盟网:京ICP备05037064号