转运(资讯保安)
背包问题
计算机科学
集合(抽象数据类型)
数学优化
皮卡
路径(计算)
算法
最短路径问题
运筹学
数学
计算机网络
计算机安全
图像(数学)
理论计算机科学
图形
人工智能
程序设计语言
作者
Eric Su,Hu Qin,Jiliu Li,Kai Pan
标识
DOI:10.1016/j.trb.2023.102831
摘要
This paper addresses a pickup and delivery problem with crowdsourced bids and transshipment (PDPCBT) in last-mile delivery, where all requests can be satisfied by either using the own vehicle fleet or outsourcing with a small compensation to crowdshippers through transshipment facilities. The crowdshippers show their willingness to deliver by submitting bids to the e-commerce company. To minimize both the travel cost of vehicles and the compensation of crowdshippers, the routes of vehicles and the selection of bids need to be optimized simultaneously. We formulate the PDPCBT into an arc-based formulation and a route-based formulation, where the latter is strengthened by the subset row inequalities. Based on the route-based formulation, we present a branch-and-price-and-cut algorithm to solve it exactly. To deal with two possible ways of serving requests, we first decompose the corresponding pricing problem into a shortest path problem and a knapsack problem, and then tackle them in the same bi-directional labeling algorithm framework. We also discuss acceleration techniques and implementation details to speed up the performance of the overall procedure. Computational experiments are conducted on a set of classic request instances, together with a set of randomly generated bid instances. With a time limit of two hours, numerical results validate the efficiency and effectiveness of the proposed algorithm. Finally, sensitivity analysis and managerial findings are also provided on the PDPCBT.
科研通智能强力驱动
Strongly Powered by AbleSci AI