In this work, a probabilistic bid generation problem with the pricing of a bundle of lanes and carrier’s vehicle routing is considered as it is an importation in transportation service procurement. Depending on the network of the vehicle, there exist multiple lanes for traveling between two locations. To solve the bid generation problem efficiently, a two-phase method approach is presented. At the core of the procedure a feasible vehicle routing problem on a multidigraph is solved by an exhaustive search algorithm to enumerate all routes concerning routing constraints and treat each route as a decision variable in the set partitioning formulation. We examine our model both analytically and empirically using a simulation-based analysis.