The timely transportation of goods to customers is an essential component of economic activities. However, heavy-duty diesel trucks that deliver goods contribute significantly to greenhouse gas emissions within many large metropolitan areas, including Los Angeles, New York, and San Francisco. To facilitate freight electrification, this paper proposes joint routing and charging (JRC) scheduling for electric trucks. The objective of the associated optimization problem is to minimize the cost of transportation, charging, and tardiness. As a result of a large number of combinations of road segments, electric trucks can take a large number of combinations of possible charging decisions and charging duration as well. The resulting mixed-integer linear programming problem (MILP) is extremely challenging because of the combinatorial complexity even in the deterministic case. Therefore, a Level-Based Surrogate Lagrangian Relaxation method is employed to decompose and coordinate the overall problem into truck subproblems that are significantly less complex. In the coordination aspect, each truck subproblem is solved independently of other subproblems based on charging cost, tardiness, and the values of Lagrangian multipliers. In addition to serving as a means of guiding and coordinating trucks, multipliers can also serve as a basis for transparent and explanatory decision-making by trucks. Testing results demonstrate that even small instances cannot be solved using the over-the-shelf solver CPLEX after several days of solving. The new method, on the other hand, can obtain near-optimal solutions within a few minutes for small cases, and within 30 minutes for large ones. Furthermore, it has been demonstrated that as battery capacity increases, the total cost decreases significantly; moreover, as the charging power increases, the number of trucks required decreases as well.
翻译:及时向客户运送货物是经济活动的一个基本组成部分,然而,重型柴油卡车运送货物,大大加剧了许多大都市地区,包括洛杉矶、纽约和旧金山的温室气体排放。为了便利货运电气化,本文件建议联合为电动卡车安排路线和收费(JRC),与此相关的优化问题的目标是尽量减少运输成本、收费和延误。由于道路段的大量组合,电动卡车可以大量结合可能的收费决定和收费期限。由此造成的混合内线性编程问题(MILP)具有极大的挑战性,因为即使在确定性案例中,组合内也存在混合内线性线性编程问题(MILP)。因此,采用一个水平上的Surrogate Lagrangian Relacation (JRC) 方法来将总的问题分解和协调到不那么复杂的卡车子问题。在协调方面,每辆卡车的子问题可以在其他小问题中单独解决,以收费、延迟、甚至拉格朗的线性编程编程问题(MILP) 问题(MILEX) 导致混合线性编程问题变得非常复杂。此外,用一个高的解算方法来证明,在数字的解算方法之后,它也可以作为解算。