The well-known benchmark process for hydrodealkylation of toluene (HDA) to produce benzene is revisited in a multi-objective approach for identifying environmentally friendly and cost-effective operation solutions. The paper begins with the presentation of the numerical tools used in this work, i.e., a multi-objective genetic algorithm and a Multiple Choice Decision Making procedure. Then, two studies related to the energy source involved in the utility production system (UPS), either fuel oil or natural gas, of the HDA process are carried out. In each case, a multi-objective optimization problem based on the minimization of the total annual cost of the process and of five environmental burdens, that are Global Warming Potential, Acidification Potential, Photochemical Ozone Creation Potential, Human Toxicity Potential and Eutrophication Potential, is solved and the best solution is identified by use of Multiple Choice Decision Making procedures. An assessment of the respective contribution of the HDA process and the UPS towards environmental impacts on the one hand, and of the environmental impacts generated by the main equipment items of the HDA process on the other hand is then performed to compare both solutions. This "gate-to-gate" environmental study is then enlarged by implementing a "cradle-to-gate" Life Cycle Assessment (LCA), for accounting of emission inventory and extraction. The use of a natural gas turbine, less economically efficient, turns out to be a more attractive alternative to meet the societal expectations concerning environment preservation and sustainable development.