基于鲁棒优化与多阶段组合拍卖的动态垃圾清运联动机制及算法研究

考虑城市商业垃圾清运分配及定价问题，对物流需求的动态性及联动性等核心属性进行凝练，将智能商业垃圾清运系统抽象为“动态垃圾清运联动（DWCS）”系统。研究面向DWCS的鲁棒优化方法与多阶段组合拍卖机制：“通过鲁棒优化方法，事前调整车辆调度等方案，前瞻性地缓解需求变动对DWCS机制的干扰；结合多阶段组合拍卖机制，事后调整资源配置等方案，后顾性地削减需求变动对系统绩效的影响”。第一，针对事前需求扰动，将鲁棒优化中的不确定集抽象为几类线性规划约束，并将其纳入车辆路径优化模型和资源配置模型；第二，针对需求联动性及事后需求扰动，构建基于VCG思想和前景理论的多阶段组合拍卖机制，保证机制的有效性和公平性；第三，针对资源配置-车辆路径双层NP-难问题，构建基于变邻域搜索（VNS）和禁忌搜索（TS）的混合启发式算法，保证算法的效率和质量。最后，项目成果拟在具有典型需求特征的大型商业垃圾清运企业进行应用测试。

This project considers the allocation and pricing problems of city commercial waste collection, in which the key features of logistics demand such as dynamics and synchronization are incorporated, and the intelligent commercial waste collection system is abstracted as the “dynamic waste collection synchronization (DWCS)” system. The robust optimization method and multi-stage combinatorial auction mechanism for DWCS are proposed; that is, “the impact of ex ante demand disturbance on the DWCS mechanism can be alleviated through a prior vehicle routing adjustment policy based on the robust optimization method, and meanwhile a real-time reallocation scheme based on the multi-stage combinatorial auction mechanism can reduce the influence of ex post demand disturbance on the overall system performance.” Firstly, regarding the ex ante demand disturbance problem, the uncertainty set in robust optimization is abstracted into several types of linear programming constraints and then incorporated into the vehicle routing model and resource allocation model. Secondly, regarding the ex post demand disturbance and synchronization problem, a multi-stage combinatorial auction based on VCG mechanism and prospect theory is designed to ensure the effectiveness and fairness. Thirdly, regarding the two-layer NP-hard allocation-routing problem, a hybrid heuristic algorithm based on variable neighborhood search (VNS) and tabu-search (TS) is constructed to ensure the efficiency and quality. Finally, the analytical and experimental results of this project will be extensively tested based on the data provided by the large commercial waste collection enterprises with typical demand characteristics.