Capacitated Slugging Dynamic Programming

Def 1: A slugging graph G = (V, E), is a directed acyclic graph where V = {T1, T2, ..., Tm} is a set of trips and E is a set of directed edges between nodes that is transitive, i.e. if (Ti, Tj) in E and (Tj, Tk) in E, then (Ti, Tk) in E.

Def 2: Given a slugging graph G = (V, E), a slugging plan Gs = (V, Es), Es in E, is a subgraph of G that satisfies the following conditions: (i) For all (Ti, Tj) in Es, there is no k != j such that (Ti, Tk) in Es; (ii) For all (Ti, Tj) in Es, there does not exist k suck that (Tk, Ti) in Es.

Basically, (i) says that Ti can be merged into at most 1 other trip and (ii) says that Ti can be merged into another trip if and only if there is no other Tk that has been merged into Ti.

Def 3: Given a slugging graph G = (V, E), a benefit is a value associated with each edge (Ti, Tj) in E. The value of benefit is given by function B(Ti, Tj) in R+. The value of B depends only on the sorce edge, i.e. B(Ti, Tj) = B(Ti, Tk) = B(Ti, Tm) and so on and so forth.

Def 4: Total benefit is the summation of B(Ti, Tj) in the slugging plan Gs = (V, Es), i.e. (Ti, Tj) in Es, B(Gs).

Def 5: Each trip Ti has number of passengers and number of available seats. If Ti is merged into Tj, passengers of Ti occupy some available seats of Tj. Number of available seats of Tj decreases so. If Ti has more passengers than available seats in Tj, Ti cannot be merged into Tj and, therefore, there is no (Ti, Tj) in Es.

Problem: Given a slugging graph G = (V, E) and definitions 1-5, find a slugging plan Gs = (V, Es), Es in E, that has maximal total benefit B(Gs).


For a detailed description of the problem, visit this link and see subsection 3.3.


I have to solve this problem using Dynamic Programming. It seems to me related to 0-1 Knapsack to some extent. For example, deciding whether or not to merge Ta, Tb and Tc into Tj is similar to having objects a, b and c and try to fit then into a bag j in a way the profit is maximum and bag capacity is preserved. However, Ta, Tb and Tc may become a bag rather than an object in this problem. Based on that, I have not been able to find the optimal substructure to start thinking about Dynamic Programming details. Could anyone lend me a hand on this?