Routing Algorithm

[system]

So, I’ve got kind of a crazy difficult (to me anyway), and I think the smartest people in the world are just the ones to solve it or at least point me in the right direction.

I am creating a Web application that allows customers to automatically book their own appointments online and assigns them to technicians. Different technicians have different skills. So, for instance, an HVAC tech might be able to install or size an HVAC unit, but not repair it. A plumber might be able to do.electrician work.

So if there were an electrical job, we have so many technicians who could do it. The problem is how to assign which jobs to whom. Basically, I need an algorithm that calculates the shortest possible routes for the technicians.

Sounds pretty simple, right? Yeah, I guess so.

…oh but wait, there is one more thing though. Each project takes a certain number of hours with a certain variance, and there is a limited time span to see each customer. So there are morning (8a-12p), afternoon (12p-4p), evening (4p-8p), and night appointments. So a plumber might have a call that takes two hours, 15 minutes, one hour, and 45 minutes in one morning (including travel time).

The customers will also provide a variety of time slots that will work for them. So a customer could select a morning appointment on Friday afternoon appointment on Tuesday and a forth.

So, we’ve got multiple customers with multiple.convenient appointment times, multiple technicians with different skills, and different lengths of time per appointment for which we need routes.

Then we’ve got to make sure that we’re not wasting skill. So we wouldn’t want a plumber/electrician doing an electrician call, when we’ve got an extra plumber not assigned any work.

As an added bonus feature, it needs to update in real time, every time someone books an appointment.

We’ve also got customers who will need a specific time, certain jobs that will need a specific tech (i.e. for a service failure), and these will be set by a human, and the system will need to work around it.

[JimL]

So now you know what challenges the schools have when they plan thei schedules

I am creating a Web application that allows customers to automatically book their own appointments online and assigns them to technicians. Different technicians have different skills. So, for instance, an HVAC tech might be able to install or size an HVAC unit, but not repair it. A plumber might be able to do.electrician work.

Set up a set of services and what they require, something like this:

[php]CREATE TABLE service
(
id int auto_increment primary key,
type varchar(30),
description varchar(255)
);

INSERT INTO service
(type, description)
VALUES
(‘HVAC installation’, ‘Some description’),
(‘HVAC repair - electric’, ‘Some description’),
(‘HVAC repair - plumbing’, ‘Some description’),
(‘HVAC repair - general’, ‘Some description’);

CREATE TABLE technician
(
id int auto_increment primary key,
type varchar(30),
description varchar(255)
);

INSERT INTO technician
(type, description)
VALUES
(‘Electrician’, ‘Some description’),
(‘Plumber’, ‘Some description’);

CREATE TABLE service_hours
(
id int auto_increment primary key,
service_id int,
technician_id int,
hours int,
description varchar(255)
);

INSERT INTO service_hours
(service_id, technician_id, hours, description)
VALUES
(1, 2, 2, ‘Plumbing’),
(1, 1, 5, ‘Electricity’),
(2, 1, 1, ‘Electricity repair 1 hour’),
(3, 2, 1, ‘Plumbing repair 1 hour’),
(4, NULL, 1, ‘General repair 1 hour’);[/php]

Then you can run queries for ie service 1 - HVAC installation

[php]SELECT *
FROM service
WHERE id = 1;

SELECT technician_id, hours, description
FROM service_hours
WHERE service_id = 1;[/php]

[code]ID TYPE DESCRIPTION
1 HVAC installation Some description

TECHNICIAN_ID HOURS DESCRIPTION
2 2 Plumbing
1 5 Electricity[/code]

[hr]

The worst part is obviously the algoritm you mention for reserving time. It is further complicated if you want the user to get a quick/immidiate response. If not you could get bookings and try to distribute hours on a weekly basis, meaning you have some data to try to mix and match to the work week.

Since you probably want the user to get a immidiate booking confirmation you will just have to assign it to the first and best available time slot.

So just fetch all employees, their profession (where profession is the one you need) and their reservations/bookings. Then loop through them to find the first one who has the spesified number of hours available (with any other filters like time/day/etc) and book him.