{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/42238"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/42238","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fuel minimization of a moving vehicle in suburban traffic","abstract":"\"In this thesis we study how a driver could use traffic light information in order to adapt his speed profile to save fuel. The mission is given by a final destination to reach (through a set of traffic lights) within a specific deadline and the objective is to minimize the fuel consumption. We assume that the speed between each traffic light is constant and we do not take into account the effects of acceleration and gear shifting. Also, we use an existing model for the fuel consumption which depends quadratically on the speed of the vehicle. For simple cases (one traffic light), we derive analytical results using basic optimization theory and the Karush-Kuhn-Tucker (KKT) necessary conditions for optimality. Thus, we show that the best strategy is not to wait at a traffic light. This is basically due to the low fuel efficiency at slow speeds. However, for more complex and realistic cases (with more traffic lights), it seems hard to obtain analytical results. Therefore, we use Dijkstra's shortest path algorithm to discretize our decision problem. By \"\"setting nodes\"\" at each distance where there is a traffic light, we can model a realistic situation with an equivalent discrete graph with non negative edge costs. Each node represents a set of coordinates (time and distance from the origin) and the weight between two nodes is the fuel consumption to go from one node to another node. Dijkstra's algorithm finds the shortest path to go from a source to a destination and therefore it gives the optimal speed profile with respect to fuel minimization. We applied this approach to both fuel minimization and time minimization problems. We also compare the optimization policy found by Dijkstra's algorithm with the one step ahead policy (minimization at each step without knowing the future). We observed that in certain cases, the optimal speed profile found with Dijkstra's algorithm and the one found with one step ahead optimization are the same. This is interesting for two reasons. First, Dijkstra's algorithm is computationally expensive as opposed to one step ahead optimization. Second, Dijkstra's algorithm requires to know all the information of traffic lights (timing and distance data) whereas one step ahead optimization only needs the information of the next traffic light.\"","abstract_html":""In this thesis we study how a driver could use traffic light information in order to adapt his speed profile to save fuel. The mission is given by a final destination to reach (through a set of traffic lights) within a specific deadline and the objective is to minimize the fuel consumption. We assume that the speed between each traffic light is constant and we do not take into account the effects of acceleration and gear shifting. Also, we use an existing model for the fuel consumption which depends quadratically on the speed of the vehicle. For simple cases (one traffic light), we derive analytical results using basic optimization theory and the Karush-Kuhn-Tucker (KKT) necessary conditions for optimality. Thus, we show that the best strategy is not to wait at a traffic light. This is basically due to the low fuel efficiency at slow speeds. However, for more complex and realistic cases (with more traffic lights), it seems hard to obtain analytical results. Therefore, we use Dijkstra's shortest path algorithm to discretize our decision problem. By ""setting nodes"" at each distance where there is a traffic light, we can model a realistic situation with an equivalent discrete graph with non negative edge costs. Each node represents a set of coordinates (time and distance from the origin) and the weight between two nodes is the fuel consumption to go from one node to another node. Dijkstra's algorithm finds the shortest path to go from a source to a destination and therefore it gives the optimal speed profile with respect to fuel minimization. We applied this approach to both fuel minimization and time minimization problems. We also compare the optimization policy found by Dijkstra's algorithm with the one step ahead policy (minimization at each step without knowing the future). We observed that in certain cases, the optimal speed profile found with Dijkstra's algorithm and the one found with one step ahead optimization are the same. This is interesting for two reasons. First, Dijkstra's algorithm is computationally expensive as opposed to one step ahead optimization. Second, Dijkstra's algorithm requires to know all the information of traffic lights (timing and distance data) whereas one step ahead optimization only needs the information of the next traffic light."","abstract_has_math":false,"creators":["Galpin, Thomas"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Aerospace Engineering","degree_department":null,"school":null,"contributors":["Voulgaris, Petros G."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-02-03T19:28:51Z","date_published":"2013-02-03T19:28:51Z","updated_at":"2026-07-22T22:25:33Z","subjects":["Fuel minimization","optimization","shortest path problem","Dijkstra's algorithm","traffic light"],"languages":["en"],"rights":["Copyright 2012 Thomas Philippe Henri"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/42238","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Voulgaris, Petros G."]},{"key":"dc:creator","label":"Author","values":["Galpin, Thomas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-02-03T19:28:51Z","2012-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Aerospace Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Fuel minimization","optimization","shortest path problem","Dijkstra's algorithm","traffic light"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 Thomas Philippe Henri"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/42238"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"In this thesis we study how a driver could use traffic light information in order to adapt his speed profile to save fuel. The mission is given by a final destination to reach (through a set of traffic lights) within a specific deadline and the objective is to minimize the fuel consumption. We assume that the speed between each traffic light is constant and we do not take into account the effects of acceleration and gear shifting. Also, we use an existing model for the fuel consumption which depends quadratically on the speed of the vehicle. For simple cases (one traffic light), we derive analytical results using basic optimization theory and the Karush-Kuhn-Tucker (KKT) necessary conditions for optimality. Thus, we show that the best strategy is not to wait at a traffic light. This is basically due to the low fuel efficiency at slow speeds. However, for more complex and realistic cases (with more traffic lights), it seems hard to obtain analytical results. Therefore, we use Dijkstra's shortest path algorithm to discretize our decision problem. By \"\"setting nodes\"\" at each distance where there is a traffic light, we can model a realistic situation with an equivalent discrete graph with non negative edge costs. Each node represents a set of coordinates (time and distance from the origin) and the weight between two nodes is the fuel consumption to go from one node to another node. Dijkstra's algorithm finds the shortest path to go from a source to a destination and therefore it gives the optimal speed profile with respect to fuel minimization. We applied this approach to both fuel minimization and time minimization problems. We also compare the optimization policy found by Dijkstra's algorithm with the one step ahead policy (minimization at each step without knowing the future). We observed that in certain cases, the optimal speed profile found with Dijkstra's algorithm and the one found with one step ahead optimization are the same. This is interesting for two reasons. First, Dijkstra's algorithm is computationally expensive as opposed to one step ahead optimization. Second, Dijkstra's algorithm requires to know all the information of traffic lights (timing and distance data) whereas one step ahead optimization only needs the information of the next traffic light.\"","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-12-13T20:01:20Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Galpin_Thomas.pdf: 812079 bytes, checksum: 47d4b7d718e0645b93f19c84b9b0b2ff (MD5)","Made available in DSpace on 2013-02-03T19:28:51Z (GMT). No. of bitstreams: 2 Thomas_Galpin.pdf: 812079 bytes, checksum: acaf84a2d664978cbad283942280679d (MD5) license.txt: 4062 bytes, checksum: 2553c37f6c59989c91c34557d5c28a43 (MD5)"]},{"key":"dc:title","label":"Title","values":["Fuel minimization of a moving vehicle in suburban traffic"]}]}],"canonical_facts":{"dc:contributor":["Voulgaris, Petros G."],"dc:creator":["Galpin, Thomas"],"dc:date":["2013-02-03T19:28:51Z","2012-12"],"dc:description":["\"In this thesis we study how a driver could use traffic light information in order to adapt his speed profile to save fuel. The mission is given by a final destination to reach (through a set of traffic lights) within a specific deadline and the objective is to minimize the fuel consumption. We assume that the speed between each traffic light is constant and we do not take into account the effects of acceleration and gear shifting. Also, we use an existing model for the fuel consumption which depends quadratically on the speed of the vehicle. For simple cases (one traffic light), we derive analytical results using basic optimization theory and the Karush-Kuhn-Tucker (KKT) necessary conditions for optimality. Thus, we show that the best strategy is not to wait at a traffic light. This is basically due to the low fuel efficiency at slow speeds. However, for more complex and realistic cases (with more traffic lights), it seems hard to obtain analytical results. Therefore, we use Dijkstra's shortest path algorithm to discretize our decision problem. By \"\"setting nodes\"\" at each distance where there is a traffic light, we can model a realistic situation with an equivalent discrete graph with non negative edge costs. Each node represents a set of coordinates (time and distance from the origin) and the weight between two nodes is the fuel consumption to go from one node to another node. Dijkstra's algorithm finds the shortest path to go from a source to a destination and therefore it gives the optimal speed profile with respect to fuel minimization. We applied this approach to both fuel minimization and time minimization problems. We also compare the optimization policy found by Dijkstra's algorithm with the one step ahead policy (minimization at each step without knowing the future). We observed that in certain cases, the optimal speed profile found with Dijkstra's algorithm and the one found with one step ahead optimization are the same. This is interesting for two reasons. First, Dijkstra's algorithm is computationally expensive as opposed to one step ahead optimization. Second, Dijkstra's algorithm requires to know all the information of traffic lights (timing and distance data) whereas one step ahead optimization only needs the information of the next traffic light.\"","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-12-13T20:01:20Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Galpin_Thomas.pdf: 812079 bytes, checksum: 47d4b7d718e0645b93f19c84b9b0b2ff (MD5)","Made available in DSpace on 2013-02-03T19:28:51Z (GMT). No. of bitstreams: 2 Thomas_Galpin.pdf: 812079 bytes, checksum: acaf84a2d664978cbad283942280679d (MD5) license.txt: 4062 bytes, checksum: 2553c37f6c59989c91c34557d5c28a43 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/42238"],"dc:language":["en"],"dc:rights":["Copyright 2012 Thomas Philippe Henri"],"dc:subject":["Fuel minimization","optimization","shortest path problem","Dijkstra's algorithm","traffic light"],"dc:title":["Fuel minimization of a moving vehicle in suburban traffic"],"dc:type":["text"],"thesis:degree_discipline":["Aerospace Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:33Z"}