حمل‌و‌نقل بخش قابل‌توجهی از تولید ناخالص ملی هرکشوری را به خود اختصاص می­دهد و بخش بزرگی از تولید آلاینده­ها در این حوزه رخ می­دهد. به همین دلیل در سال‌های اخیر تلاش زیادی برای کاهش آلاینده­های تولید شده توسط وسائل نقلیه صورت گرفته است. از جمله مسائل مطرح در زمینه‌ی حمل‌و‌نقل، مسئله‌ی مسیریابی وسائل نقلیه‌ است که می‌توان محدودیت‌های مختلفی را بر روی این مسئله اعمال و آن را به جهان واقع نزدیک‌‌تر کرد. مسائل مسیریابی وسائل نقلیه دوره‌ای و مسیریابی وسائل نقلیه وابسته به زمان از کاربردی‌ترین مسائل موجود در لجستیک هستند. مسئله مسیریابی وسائل نقلیه دوره‌ای به‌ویژه در لجستیک شهری به خوبی قابل مشاهده است چرا که گاهی مشتریان یک تولید کننده نیاز به ارضای تقاضای خود در طول افق برنامه‌ریزی دارند. همچنین با توجه به این مهم که زمان جزء لاینفک سیستم حمل‌و‌نقل شهری است، و با در نظر گرفتن این موضوع که آلودگی ناشی از سوخت وسائل نقلیه، به یک مشکل جدی و کلان در سال های اخیر تبدیل شده است، لذا در این تحقیق با ترکیب دو مدل مسیریابی وسائل نقلیه دوره­ای و مسیریابی وسائل نقلیه وابسته به زمان، همزمان با در نظر گرفتن عواملی همچون بار، سرعت وسائل نقلیه و شیب جاده، به بهینه­سازی تولید آلاینده‌ها در مسیریابی وسائل نقلیه پرداخته شده است. از طرفی به دلیل تأثیر در نظرگرفتن آلترناتیوهای مختلف برای انتخاب مسیرهای بین دو گره، در رسیدن به سرعت بهینه و به‌تبع آن کاهش آلودگی، در این پژوهش علاوه بر موارد فوق فرض وجود گراف چند آلترناتیوی نیز در نظرگرفته شده است. در ادامه با توجه به عوامل ذکر شده یک مدل برنامه‌ریزی غیر خطی عدد صحیح مختلط به‌منظور کاهش آلاینده‌های تولید شده توسط وسائل نقلیه، ارائه گردیده است. با توجه به Np-hard بودن مسئله‌ی مطرح شده به منظور حل بهینه‌ی مدل از دو الگوریتم‌ فراابتکاری جستجوی همسایگی تطبیقی بزرگ و جستجوی همسایگی بزرگ تطبیقی پیشنهادی تحت عنوان جستجوی همسایگی بزرگ تطبیقی موازی استفاده گردیده است. در نهایت پس از مقایسه‌ی عددی بین الگوریتم‌ها نتایج حاکی از بهبود جواب­ها توسط الگوریتم پیشنهادی را دارد.