Abstract: Delivery and installation are critical links in the last-mile logistics of home appliances. Their efficiency has directly affected customer satisfaction. In the past, most logistic enterprises used an asynchronous delivery and installation model, where installers offered secondary services separately after the product was delivered to the customer. Although it increases the delivery efficiency and flexibility of installation, the model also results in more frequent truck visits, which raise the overall cost and detracts from the customer's satisfaction with after-sales care. Therefore, many home appliance enterprises have adopted a synchronous delivery and installation model in recent years, requiring installers to simultaneously perform delivery and installation services. However, installation dominates a large part of the service time. It reduces multiple truck visits than the asynchronous delivery and installation model, leading to lower efficiency and reduced customer satisfaction during peak business hours. Furthermore, monotonously adopting the synchronous delivery and installation strategy will affect the distribution efficiency of the orders that do not need to be installed. Especially subject to available installers, some orders' delivery and installation service may take place later than promised, affecting customer satisfaction, corporate reputation, and market competitiveness.
In this context, this paper addresses the vehicle routing problem in mixed synchronous/asynchronous delivery and installation of home appliances, that is, delivery and installation services for each customer can be synchronized or separated. By incorporating both characters, we expect to realize the overall efficiency of the delivery and installation and offer a more flexible schedule for the delivery vehicle route and service plan. A mixed-integer linear programming model is then developed for the appliance delivery and installation routing problem with soft time windows and constraints on vehicle capacity, available vehicles, and maximum working time. The objective is to minimize the total appliance delivery and installation costs, including fixed dispatching vehicle costs, vehicle travel costs, and penalty costs for delayed installation. Since it is an NP-hard problem that cannot be solved by exact solution methodologies within acceptable computational time, an improved genetic algorithm (GA) is tailored to solve the model. We assess the performance of the proposed genetic algorithm with numerical experiments. The results show that: (1)GA outperforms Gurobi in computation time in small-scale numerical trials. When it comes to large-scale problems, Gurobi struggles to find the best solution within 3600s, while GA can also obtain a better solution. (2)For medium-scale cases, GA works better than the adaptive large neighborhood search algorithm (ALNS) from existing research in computation time and solution quality. In a few experiments, ALNS is only marginally better than GA.
Finally, we conduct a case analysis of real-life order data from a logistics and distribution center. We explore different delivery and installation strategies and evaluate the proposed models' operational performance compared to the tedious implementation of synchronous or asynchronous delivery and installation. The results reveal that: (1)The mixed delivery and installation model achieves maximum cost savings by operating the synchronous delivery and installation as much as possible while utilizing an asynchronous delivery and installation strategy for the remaining customer orders. (2)Additionally, the above model realizes a 30% reduction in average customer delivery completion time and requires fewer delivery trucks and installers. (3)Besides, delivery efficiencies increase significantly with greater separation of deliveries and installations. In conclusion, the proposed mode can not only guarantee the synchronous delivery and installation model as much as possible but also save delivery vehicles and installation personnel, significantly improve delivery efficiency, and reduce the total cost, which can provide decision support for the vehicle routing and scheduling scheme in appliances delivery and installation.
In further study, the synchronous/asynchronous delivery and installation can be extended to multiple periods, dynamic orders, and other characteristics and cover more factors in real life.

Key words: appliances delivery and installation, vehicle routing problem, time windows, genetic algorithm

摘要： 结合送装分离模式的灵活性和配送效率,研究家电送装一体和送装分离模式相结合的车辆路径问题,以寻求兼顾客户服务体验和整体送装效率的最优送装路径方案。基于混合整数线性规划方法建立了以送装总成本最小化为目标、带软时间窗的家电送装路径优化模型,并根据模型特点针对性设计了改进的遗传算法进行求解,通过算例验证了所提模型和算法的有效性。最后,结合实例比较了上述混合送装模式相对于送装一体和送装分离模式的优化方案绩效,以期为家电送装路径优化提供辅助决策支持。

关键词: 家电送装, 车辆路径问题, 时间窗, 遗传算法