Truthful coordination at loading docks: A market design approach for transportation logistics (TRUCKS)

研究了运输物流中承运人协调的电子市场机制设计。在零售商的装货码头等待时间过长是一种普遍现象，导致零售运输物流效率严重低下。为这类问题设计协调机制具有挑战性，原因有两个：首先，机制应该抵制操纵，并设置激励机制，以真实地披露对运营商的偏好。其次，如果一种机制是真实的，那么计算有效的时隙分配是一个组合的、计算困难的问题。该问题对于网络经济中出现的许多具有多个决策者的计算困难的分配问题具有代表性。我们比较了现有的组合拍卖机制以实现运营商之间的协调，并在现有近似方法的基础上进行了扩展。我们的目标是通过利用近最佳分配的研究结果来提高解决方案的质量。对于大多数现实世界的问题，人们可以非常快地找到大型实例的组合优化问题的近最优解，同时证明最优性是困难的。虽然卡车采购中拍卖很常见，但承运人愿意为装货码头预订付费的意愿很低。问题是，是否也可以在不付款的情况下实现协调；即，在没有货币转移的情况下分配资源的匹配市场。因此，我们还分析和扩展了现有的关于互补性匹配的工作，并考察了平均情况下的可行性违规程度和效率；由于出行和服务时间的不确定性，我们最后考虑了分配决策中考虑供需变化的机制。我们在以前关于在线协调的工作的基础上，研究了哪些机制和近似技术可以应用于我们的设置。由此产生的机制应该有助于信息系统和运筹学接口上的一个重要但具有挑战性的问题：为计算困难的分配问题设计抵抗战略操纵的机制。这一领域的进展将产生重大影响，远远超出运输物流问题。除了我们的理论分析，我们的目标是基于之前与几个行业合作伙伴的合作所获得的现场数据进行广泛的数值实验。

We study the design of electronic market mechanisms for the coordination of carriers in transportation logistics. Long waiting times at loading docks of retailers are a widespread phenomenon causing substantial inefficiencies in retail transportation logistics. The design of coordination mechanisms for such problems is challenging for two reasons: First, mechanisms should be resistant to manipulation and set incentives for truthful revelation of preferences for carriers. Secondly, if a mechanism is truthful, computing an efficient allocation of time slots is a combinatorial, computationally hard problem. The problem is representative for many computationally hard allocation problems with multiple decision makers as they arise in a networked economy.We compare existing combinatorial auction mechanisms to achieve coordination among carriers and develop extensions based on existing approximation approaches. We aim at an improved solution quality by leveraging results from research on near-optimal allocations. For most real-world problems one can find near-optimal solutions of combinatorial optimization problems for large instances very fast, while proving optimality is intractable.While auctions are common for truckload procurement, carriers' willingness to pay for loading dock reservations is low. The question arises if coordination can also be achieved without payments; i.e., with matching markets where resources are allocated without monetary transfers. Hence, we additionally analyze and extend existing work on matching with complementarities, which commonly approximates feasibility, and investigate the degree of average-case feasibility violations and efficiency.Due to uncertainties in travel and service times, we finally consider mechanisms that take changes of supply and demand in allocation decisions into account. We build on prior work on online coordination and investigate which mechanisms and approximation techniques can be applied to our settings.The resulting mechanisms should contribute to an important, yet challenging problem at the interface of information systems and operations research: the design of mechanisms that are resistant to strategic manipulation for computationally hard allocation problems. Progress in this area would have substantial impact far beyond the transportation logistics problem. Apart from our theoretical analyses, we aim at extensive numerical experiments based on field data available from previous cooperations with several industry partners.