Approximation algorithm for generalized budgeted assignment problems and applications in transportation systems

Motivated by a transit line planning problem in transportation systems, we investigate the following capacitated assignment problem under a budget constraint. Our model involves L bins and P items. Each bin l has a utilization cost c_l and an n_l-dimensional capacity vector. Each item p has an n_l-dimensional binary weight vector r_lp, where the 1s in r_lp (if any) appear in consecutive positions, and its assignment to bin l yields a reward v_lp. The objective is to maximize total rewards through an assignment that satisfies three constraints: (i) the total weights of assigned items do not violate any bin's capacity; (ii) each item is assigned to at most one open bin; and (iii) the overall utilization costs remain within a total budget B.
We propose the first randomized rounding algorithm with a constant approximation ratio for this problem. We then apply our framework to the motivating transit line planning problem, presenting corresponding models and conducting numerical experiments using real-world data. Our results demonstrate significant improvements over previous approaches in addressing this critical transportation challenge.
© 2024 Elsevier B.V.