Seminar on January 8, 2015



Vehicle Routing with Soft Time Windows and Stochastic Travel Times:

A Column Generation and Branch-and-Price Solution Approach


Duygu Taş,

(HEC Montréal and CIRRELT, Montréal, Canada)



We study a vehicle routing problem with soft time windows and stochastic travel times. In this problem, we consider stochastic travel times to obtain routes which are both efficient and reliable. In our problem setting, soft time windows allow early and late servicing at customers by incurring some penalty costs. The objective is to minimize the sum of transportation costs and service costs. Transportation costs result from three elements which are the total distance traveled, the number of vehicles used and the total expected overtime of the drivers. Service costs are incurred for early and late arrivals; these correspond to time-window violations at the customers. We apply a column generation procedure to solve this problem. The master problem can be modeled as a classical set partitioning problem. The pricing subproblem, for each vehicle, corresponds to an elementary shortest path problem with resource constraints. To generate an integer solution, we embed our column generation procedure within a branch-and-price method. Extensive computational results are obtained by experimenting with well-known problem instances.


Short Bio: 

Dr.Duygu Taş holds a B.Sc. degree in Mechanical Engineering from the Faculty of Engineering at Boğaziçi University (2006). She received her M.Sc. degree in Industrial Engineering from the Faculty of Engineering and Natural Sciences at Sabancı University (2008). She carried out her Ph.D. studies at the School of Industrial Engineering and Innovation Sciences at the Eindhoven University of Technology (2009–2013). She conducted a part of her Ph.D. research at CIRRELT - Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation. Since completing her Ph.D., she has been working as a post-doctoral fellow at HEC Montréal and CIRRELT. Dr.Taş has published her research in leading academic journals including Computers & Operations Research, European Journal of Operational Research, and Transportation Research Part C: Emerging Technologies. She frequently presents her research at academic and professional conferences, and also serves as a reviewer for numerous scientific international journals in operations research. Her research is mainly focused on production and inventory planning under uncertainty, transportation planning under uncertainty, and airline crew scheduling.


All interested are cordially invited.  


DATE:  January 8, 2015 

TIME:  Thursday, 14:00-15:00