# An electronics manufacturing company collects its outdated/end-of-life products from its customers in order recycle them.

IE 342 – FALL 2016
Assignment
(Due: January 13, 2017 at 11:55pm)
You can work in groups of 2 or 3 people (not more than 3)
An electronics manufacturing company collects its outdated/end-of-life products from its
customers in order recycle them. Currently, the company is focusing on two products and
wants to design the collection plan for these two products. After these two products are
collected from the customers, they are transported to recycling facilities by collection
vehicles. The manufacturer has two collection vehicles used in this collection activity. Each
vehicle collects one type of product from the customers and delivers them to the relevant
recycling facility. The manufacturer has two recycling facilities, one for each product. Vehicle
1 collects product 1 from the customers, and delivers them to the Recycling Facility 1, and
similarly, Vehicle 2 collects product 2 from the customers and delivers them to the Recycling
Facility 2. Both vehicles start their travel from the depot, and stop at a recycling facility.
Because of the small size of the products, you can assume that vehicles re uncapacitated.
The company’s goal is to collect the products from the customers and deliver them to the
recycling facilities with minimum total transportation cost. Note that a customer may have
both products to be collected and recycled. In order to decrease the total transportation
cost, one vehicle may “help” the other vehicle by collecting its products from the customers
and drop them off at another customer location in order for the other vehicle to collect it.
Hence, vehicle
i does not have to visit a certain customer if that customer does not have any
product
i to be collected or those products are collected by the other vehicle and dropped at
another customer location.
You are given the following notation in order to solve the company’s problem:
N: number of customers
S = {1, 2, …, N}: set of customers
0: node representing the depot
N+1: node representing the recycling facility for the first product
N+2: node representing the recycling facility for the second product
Using the notation above, the problem can be defined on a graph
G = (V,E) where V =
{0,1,2,…,
N, N+1, N+2} is the set of nodes and E is the set of edges. Assume that the graph is a
complete graph, that is, it is possible to go from any node
i to any other node j directly. The
cost of going from node
i to node j is denoted by cij. Customer k (k ϵ S) has