The network design problem (NDP) is a bi -level problem with integer and decimal variables that aims to minimize the users' total cost under the budget constraints. Although utilizing variable demand models will theoretically change the NDP’s result, the demand was assumed to be fixed and known in the literature. I n this paper, a mathematical analysis will be presented to justify the importance of using variable demand in the discrete network design problem (DNDP). The DNDP for Sioux -falls network will be solved in both variable and fixed demand conditions by using total enumeration (in the upper -level) and Frank -Wolf (in the lower -level) method. The result shows that DNDP findings for variable and fix demand conditions have significant differences, especially in the mid -budget level. Keywords : network design proble m, variable demand, Frank -Wolf method 1. INTRODUCTION Making decisions about how to allocate budget to potential projects is a major concern in transportation studies. NDP defines as selecting a subset of feasible options (projects), like building a new road, expanding an existing road , which minimizes the users’ total cost and does not exceed a certain budget level. Theoretically, NDP can be formulated as a two -level problem with integer and decimal variables. In the upper -level problem, the number of integer variables is equal to the number of projects, and in the lower -level problem, the number of decimal variables is equal to the number of flow variables in the network’s links. NDP had better study with realistic assumption s, or the sys tem managers will be misled. A fundamental parameter that significantly influences the NDP result is users ' travel demand , which can be deemed either fix or variable. The trip rate between origin and destination pairs typically assumes to be fixed and know n. In reality, however, these trip rates may be influenced by the level of service on the network. For example, as congestion increases, motorists may decide to use a different mode of travel (e.g., subway), shift the time of travel (outside the design per iod), or forego some trips altogether. In order to take this phenomenon into account, the trip rate between every O -D pair in the network can be considered variable and assumed to be a function of the travel time. Although scientists believe that consideri ng variable demand can better formulate the users' behavior, this realistic assumption has never been used in the NDP yet. In this paper, static and definite traffic demand assignment with variable demand is utilized in the lower -level problem, and the total enumeration method is used to find a feasible set of projects in the upper -level problem. In addition, the effect of using variable demand assumption s on DNDP’s result will be investigated, and by comparing the results in the fix and variable demand conditions, the importance or unimportance of using variable demand assumption s will be discussed. This paper is organized as follows: First, a literature review on NDP is provided in Section 2. In the subsequent sections, DNDP formulation is extended in Sect ion 3 to integrate the problem. The proposed approaches to model the variable demand function is presented and discussed in Section 4. A mathematical analysis is provided in section 5 to discuss the importance of using variable demand in DNDP and find the condition in which DNDP with variable and fix demand have different results. Numerical examples to ascertain the performance of the proposed approach is given in Section 6. Finally, Section 7 concludes the paper. 2. LITERATURE REVIEW NDP has been continuo usly studied during the last five decades, and it is regarded as one of the most complicated concepts in transportation study because of computational difficulties in solving the mixed -integer nonlinear and bi -level program formulation. Dantzig et al. (197 9) asserted that NDP is concerned with building new streets or expanding the capacity of existing streets. NDP can be divided into three different categories; (1) discrete network design problem (DNDP), which includes discrete design decisions such as cons tructing new roads, adding new lanes, determining the directions of one -way streets, and determining the turning restrictions at intersections, (2) continuous network design problem (CNDP), which deals with continuous design decisions such as expanding the capacity of streets, scheduling traffic lights, and determining toll for some specific streets, and (3) mixed network design problem (MNDP), which concentrate on a combination of continuous and discrete decisions (Farahani et al., 2013). DNDP was first i nvestigated by Steenbrink (1974). He utilized a single optimization method to minimize total societal cost s. System optimization (SO) method was used as the traffic assignment model, the demand was deemed to be fixed and known, decision variables were new street constructing and street capacity expansion , and iterative decomposition algorithm was used to solve the problem. Leblanc (1975) used a single optimization method to minimize total travel time by considering definite user equilibrium (DUE) with fix d emand as traffic assignment model, street capacity expansion as a decision variable, and Branch and Bound algorithm as a solution method. Poorzahedy and Turnquist (1982) solved DNDP with a similar assumption to Leblanc (1975). The differences were consider ing new street constructing as well as street capacity expansion and using Branch and Backtrack heuristics algorithm instead of the Branch and Bound algorithm. Chen and Alfa (1991) solved DNDP with a single optimization method that minimizes travel and con struction cost. Stochastic user equilibrium (SUE) with fix demand was utili zed as a traffic assignment model. Branch and Bound algorithm applied to solve the upper -level problem that includes new street constructing as a decision variable, and stochastic increment assignment applied for solving the lower -level problem. Gao et al. (2005) solved DNDP with a similar assumption to Leblanc (1975) , and the differences were considering new street constructing as well as street capacity expansion and using generali zed Benders decomposition method with support function instead of Branch and Bound algorithm. Poorzahedy and Abulghasemi (2005) solved DNDP with a similar assumption to Poorzahedy and Turnquist (1982); however, the Ant Systems algorithm was applied as a so lution method. Poorzahedy and Rouhani (2007) adopt ed Poorzahedy and Turnquist 's (1982) assumptions to solve DNDP ; nonetheless, hybrids of ant systems, ant colony with a genetic algo rithm, simulated annealing and T abu search were utilized as a solution meth od. Miandoabchi and Farahani (2010) used a single optimization method to maximize reserve capacity by considering (DUE) with fix demand as traffic assignment model, street capacity exp ansion, lane allocation in two -way streets , and making some streets one-way as decision variables. H ybrid of simulated annealin g, genetic algorithm , and evolutionary simulated annealing algorithm were used as solution methods. Babazadeh et al. (2011) solved DNDP with a similar assumption to Poorzahedy and Turnquist (1982); how ever, the particle swarm optimization algorithm was applied as a solution method. Wang et al. (2013) adopted Poorzahedy and Turnquist 's (1982) assumptions to solve DNDP , and the differences were utilizing two global optimization algorithms as a solution method. These global optimization algorithms use the relation between SO and UE. Finally, Wang et al. (2015) solved DNDP with a similar assumption to Poorzahedy and Turnquist (1982); however, a global optimization method proposed as a solution method that no t only does find the optimal subset of the project but also calculates their ideal capacity. It is worth mentioning that, variable demand assumption has never been utilized in NDP yet (Farahani et al., 2013). 3. DNDP FORMULATION Let ( , )N I A be a graph representing a transportation network with node -set I and arc set A. Consider A as a set of arc projects in which AA includes link improve ment projects (e.g. , expanding an existing road) and AA consists of new project links. ay is a decision variable for link aA , and ()a yy is a decision vector tha t consists of decision variables ay . The d ecision variable ay defines whether the problem is CNDP or DNDP. In DNDP ay is a bina ry variable, selection or not selection a project, and in the CNDP ay is an integer variable. For instance, if the maximum and minimum link’s capacity are supposed to be maxC and minC , the constraint min maxC y C defines a cont inuous range for decision y . In DNDP 's decision about selection or not selection a project, expanding or not expanding a project defines with the constraint {0,1}y . Since this paper adopts DNDP , its formulation will be discussed in this section. Assume that ()A y A is a subset of selected projects in the decision y , which is shown as ( ) { 1}a A y a A y   . DNDP for finding a decision variable y in the budget level B is presented as follows. ( ) ( )( ) ( ) ( ) .. {0 , 1} ( ) ( ) ( )a a a a a a a A A y a A y aa aA aMinT y x t x x t x st DNDP c y B y a A y x y Assign y              (1) ()Ty : Network’s total time for decision y ax : Link’s flow for a A A ()atx : Travel time function for link aA in the base network ()atx : Travel time function for link aA after link improvement ay : Decision variable for link aA ()xy: Vector of links’ flow after the decision y , () ( ) ( )aa A A y x y x ac : Cost of implementing a project aA B : Budget level Assign : An assignment algorithm that finds vector ()xy for decision y In this problem, t he objective function searches for finding a decision variable ()a yy that minimizes the networks total time ()Ty . The first and second constraints are feasibility constraints for the decision variable y. The first one is a budget constraint , and the secon d one is a feasible area constraint . The third constraint is a traffic assignment model that finds the traffic flow for each network configuration and demand condition . 3.1. TRAFFIC ASSIGN MENT PROBLEM Wardrop (1952) first discussed the equilibrium condition in the transportation network. According to Wardrop’s first rule , for each O -D pair, at user equilibrium, the travel time on all used paths are equal, and less than or equal to the trave l time that would be experienced by a single vehicle on any unused path. The traffic condition that satisfies this situation is called UE (User Equilibrium). The UE problem with two fundamental assumptions would be change d to an optimization problem; (1) each link’s travel time function is only dependent on its own flow, (2) travel time function should be both positive and strictly increasing. This problem was first developed by Beckmann et al. (1956) and is presented as follows. 0min ( ) ( ) .. , 0 , , ax a a rs rs k k rs k rs rs a k ak rs kz x t d st f q r s f r s k x f a A                  (2) In this model, ax is the flow of link a, ()atx is the travel time function of link a , rs kf is flow in path k for origin -destination rs and rsq is fix and known demand between origin -destination rs . The parameter rs ak is equal to 1 if the links a lies on the path k that is related to origin - destination rs and is equal to zero otherwise . In the Beckman model, the objective function is equal to the sum of travel time functions ’ integral and has neither economic nor behavioral meaning. The first constraint indicates that the sum of path flow , which is related to an origin - destination pair should be equal to that origin -destination pair’s demand. The second constraint was mentioned to assure the feasibility of the solution , and the third constraint shows the relation between flow in the link a and the flow in the path k which is related to origin -destination rs . The optimization UE model is formulated by assuming fix and known demand between every origin -destination pairs . However, in the real condition , the demand may be influenced by the level of service. For instance, as congestion inc reases , the traveler is more likely to choose other modes of transportation. To formulate UE with variable demand consider rsq as the variable demand between origin -destination rs , which is a function of tra vel time ( ()rs rs rsq D u ). rsu is the minimum travel time between origin -destination rs and (.)rsD is a demand function between origin -destination rs . The UE with variable demand is as follows. 1 00min ( , ) ( ) ( ) .. , 0 , , 0 ,                a rsxq a rs a rs rs rs k k rs k rsz x q t d D d st f q r s f r s k q r s (3) In this model , 1(.)rsD is the inverse of demand function between origin -destination rs and the equation rs rs a k ak rs kxf   shows the relation between flow in link a and path k . The additional term in the objective function comparing to the Beckman model is the sum of the inverse of demand functions’ integrals . The firs t and second constraints were discussed previously and the third one mentioned to assure the feasibility of demand between each origin -destination. 3.2. BI-LEVEL DNDP DNDP can be expressed by using either SO or UE as an assignment model . Utilizing the SO model would result in creating a one lev el problem that is easier to solve; nonetheless, a precise result will not be obtained since the assumption is not realistic. On the other hand, using the UE model would create a bi -level formulation. Regardless of difficulties in solving the problem , this formu lation was widely used since it was based on more realistic assumptions than the one -level formulation. In this model , the upper -level is devo ted to optimizing policy makers ’ objective(s) with regard to budget constraints, and the lower -level could be UE model with either fix ed or variable demand . This paper adopts bi-level programming to solve DNDP . This problem for variable demand condition s can be shown as follows. ( ) ( )( ) ( ) ( ) .. {0 , 1} ( ) ( ) ( )a a a a a a a A A y a A y aa aA aMinT y x t x x t x st ULP c y B y a A y x y is solution of LLP y              (4) 1 ( ) ( ) 0 0 0min ( , ) ( ) ( ) ( ) .. ,() 0 , , 0              a a rsx x q a a rs a A A y a A y rs rs k rs k rs k rsz x q t w dw t w dw D d st f q r sLLP y f r s k q ( , ), ( )               rs rs a k ak r s krs x f a A A y (5) In this model, the upper -level problem searches for finding the decision variable ()a yy that minimizes the network’s total time ()Ty , and the lower -level problem is a traffic assignment model that yields a flow vector ()xy for decision y . 3.3. SOLUTION ALGORITHM In this paper , a convex combination based algorithm is used to solve the TAP with variable demand . This algorithm can be summarized as follows (Sheffi , 1985). Step 0: Initialization. Find an initial feasible flow pattern for n ax and n rsq . Set n = 1. Step 1: Update. Set ( ) nn a a at t x a . Compute 1( ) ,n rs rsD q r s . Step 2 : Direction finding. Compute the shortest path, m, between each _OD pair ,rs based on n at . rs kC is the time of path k related to origin -destination rs. Execute the assignment rule as follows: 1 1if ( ) & 0 if ( ) 0 n nrs rs rs rs m rs rs k k rs rs m rs rs kC D q g q g k m C D q g k            This assignment yields an auxiliary flow pattern n ay , n rs. With these variables, the descent direction is a vector nd with elements ()nn aayx and ()nn rs rsvq . rs kgis a temporary path variable. .; ;,      n rs rs a k ak rs k n rs rs k ky g a g r s Step 3: Move size. Find n by solving the following minimization program. ( ) ( ) 1 00min ( ) ( ) ( ) .. 01n n n n n n a a a rs a ax y x q q a rs a rsZ t d D d st                   Step 4: Flow update. Find 1n ax and 1n rsq by using equation s 1()n n n n a a a ax x y x    and 1()n n n n rs rs a aq q q    . Step 5: Convergence criterion. If the following inequality holds, terminate. Otherwise, set 1 nn and go to step 1. a a rs rs a rs aa af t q u RG ft   4. VARIABLE DEMAND Travel deman d refers to the amount and type of travel that people would choose in particular situations. Various demographic factors like employment rate and p