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

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