A profit maximization problem of equipment rental and scheduling with split services
研究了租赁平台在阶梯式租金政策下，通过拆分客户需求来最大化利润的调度问题，提出了分支定价算法并验证了拆分服务的价值。
This study addresses a scheduling problem arising from the “Rent Instead of Buy” business model where rental service platforms rent equipment from suppliers to satisfy customer requests in exchange for a lump-sum payment. Suppliers often implement piecewise linear concave charging policies to encourage longer rental duration. This policy prompts the platform to consolidate service periods into longer rental agreements for lower rental rates, potentially necessitating the splitting of a customer request among multiple facilities. We establish an integer programming model to maximize the platform’s profit, which is equal to the total revenue from serving customers minus the total rental and scheduling costs. To solve the problem, we propose two Dantzig–Wolfe decomposition reformulations and design branch-and-price algorithms accordingly. Furthermore, by exploiting the property of the concave rental cost functions, we derive the optimal structure regarding the start and end times of services, significantly reducing the subproblem’s search space. Numerical experiments based on real-life data validate the efficiency of the designed algorithms compared to commercial solvers and highlight the benefits of split services. Sensitivity analysis reveals that as the rental cost function becomes more segmented, more requests are split-serviced, but the times for splitting a request are seldom more than once.